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