Selection sort

Selection sort is one of the simple sorting techniques. The basic idea behind this technique is, in each iteration the smallest element in the list is picked up and placed in its exact position. This works as follows,

For a list of n items, we have to iterate through the list for n times.

In first iteration consider the n items, scan the list and find the smallest item. Place this item in the first position. (This will be its exact position)

Now in the second iteration, scan the list except the first item  and find the smallest

Item in the list. Place this item in the second position of the list. (This will be its exact position)

Similarly continue for n iterations.

Given below is an example c code that sorts the input list of 5 items in ascending order using selection sort technique.

#include<stdio.h>

void main()

{

int i,a[5],j,small,loc,k;

clrscr();

printf("\nEnter 5 numbers to sort ::\n");

for(i=0;i<5;i++)

scanf("%d",&a[i]);

printf("\nElements before sort : ");

for(i=0;i<5;i++)

printf("%d\t",a[i]);

for(i=0;i<4;i++)

{

small=a[i];

loc=i;

                for(j=i+1;j<5;j++)

                {

                                if(a[j]<small)

                                {

                                small=a[j];

                                loc=j;

                                }

                }

a[loc]=a[i];

a[i]=small;

}

printf("\n\nElements after sort : ");

for(i=0;i<5;i++)

printf("\t%d",a[i]);

getch();

}

Selection sort reduces the total number of swaps when compared to bubble sort. The  worst case running time will be O(n2).

• Minimum number of swaps 0 ( if the list is already sorted)
• Maximum swaps n-1
• Minimum comparisions n(n-1)/2
• Maximum comparisions n(n-1)/2

For comparison of various sorting algorithms click here