Home | | **Fundamentals of Data Structures in C** | | **Data Structures** | | **Programming and Data Structures I** | Selection sort

Selection sort or push-down sort implements selection phase in which either largest or smallest element find from the list and it is swapped to the last or first position respectively.

**SELECTION
SORT**

**Definition:**

Selection sort or push-down sort implements
selection phase in which either largest or smallest element find from the list
and it is swapped to the last or first position respectively.

**Algorithm:**

The
algorithm works as follows:

1. Find
the largest value in the list

2. Swap
it with the value in the last position

**3. **Repeat
the steps above for the remainder of the list (starting at the second position
and advancing each time)

**Implementation in C:**

#include
<stdio.h> #include<conio.h> void main()

{

int array[100], n, c, d, position, swap;
printf("Enter number of elements\n"); scanf("%d", &n);

printf("Enter %d integers\n", n); for ( c
= 0 ; c < n ; c++ )

scanf("%d",
&array[c]);

for
( c = 0 ; c < ( n - 1 ) ; c++ )

{

position = c;

for
( d = c + 1 ; d < n ; d++ )

{

if ( array[position] > array[d] )
position = d;

}

if
( position != c )

{

swap
= array[c];

array[c] = array[position]; array[position] = swap;

}

}

printf("Sorted list in ascending
order:\n"); for ( c = 0 ; c < n ; c++ )

printf("%d\n", array[c]);
getch();

}

**Execution:**

For example, consider the following
array, shown with array elements in sequence separated by commas:

The leftmost element is
at index zero, and the rightmost element is at the highest array index, in our
case, 4 (the effective size of our array is 5).

The largest element in this effective
array (index 0-4) is at index 2. We have shown the largest element and the one at
the highest index in **bold**. We then swap the element at index 2 with that
at index 4. The result is:

We reduce the effective size of the
array to 4, making the highest index in the effective array now 3. The largest
element in this effective array (index 0-3) is at index 1, so we swap elements
at index 1 and 3 (in **bold**):

The next two steps give us:

Now the list is sorted.

**Complexity Analysis:**

Selection sort
is not difficult to analyze compared to other sorting algorithms since none of
the loops depend on the data in the array.

Selecting the
lowest element requires scanning all n elements (this takes n −1 comparisons)
and then swapping it into the first position.

Finding the
next lowest element requires scanning the remaining n −1 elements and so on, ∈ for (n −1) + (n −2) + ... + 2 + 1 = n(n −1) / 2 Θ(n) comparisons.

**Insertion
Sorts**

• A
simple sorting technique that scans the sorted list, starting at the beginning,
for the correct insertion point for each of the items from the unsorted list.

• Similar
to the way people manually sort items, an insertion sort is not efficient for
large lists, but is relatively fast for adding a small number of new items
periodically.

Three insertion sort related sorting techniques are
discussed here they are

i)
Simple Insertion Sort

ii)
Shell sort

iii)
Address Calculation sort.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.