Selection Sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n²) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.

Selection sort carries out a sequence of passes over the table. At the first pass an entry is selected on some criteria and placed in the correct position in the table. The possible criteria for selecting an element are to pick the smallest or pick the largest. If the smallest is chosen then, for sorting in ascending order, the correct position to put it is at the beginning of the table. Now that the correct entry is in the first place in the table the process is repeated on the remaining entries. Once this has been repeated n-1 times the n-1 smallest entries are in the first n-1 places which leaves the largest element in the last place. Thus only n-1 passes are required. The algorithm can be described as follows:

for i from 1 to n-1
   {
    Find smallest element in ith to nth entries.
    Exchange this element with ith entry.
   }

For example consider the following example of selection sort being carried out on a sample set of data:

9 2 5 7 4 8   on pass 1 look for smallest in 1st to 6th
              swap 2nd with first giving
2 9 5 7 4 8   on pass 2 look for smallest in 2nd to 6th
              swap 5th with second giving
2 4 5 7 9 8   on pass 3 look for smallest in 3rd to 6th
              swap 3rd with third giving
2 4 5 7 9 8   on pass 4 look for smallest in 4th to 6th
              swap 4th with fourth giving
2 4 5 7 9 8   on pass 5 look for smallest in 5th to 6th
              swap 5th with 6th giving
2 4 5 7 8 9   sorted.

The algorithm is now written in C++. Of course the limits 1 to n-1 in the above now become 0 to n-2 because array subscripts start at 0.

for (i = 0; i < n-1; i++)
  {
     // find smallest entry in ith to n-1 th place
     // p is subscript of smallest entry yet found
   p = i;
   for (j = i+1; j < n; j++)
     if (a[j]<a[p])
       p = j;
     // exchange pth element with ith element
   t = a[p];
   a[p] = a[i];
   a[i] = t;
  }

Note that when finding the smallest element the index p is the index of the smallest value found so far. Only after the position of the minimum value has been found does the actual interchange take place.
In assessing the efficiency of sorting routines it is usual to count the number of comparisons made between keys and the number of exchanges of table entries.
To count the number of comparisons in the above algorithm note that the outer loop is traversed n-1 times. At the ith execution of the outer loop the inner loop is executed as j takes values from i+1 to n-1, that is n-i-1 times. Hence the total number of comparisons made is

(n-1)+(n-2)+.....+3+2+1 = n(n-1)/2

So on comparisons selection sort is order( ). Thus doubling the number of entries to be sorted will mean that four times as many comparisons will be made.
Inside the outer loop entries are exchanged three times. Thus the total number of exchanges is 3*(n-1), i.e. of order(n).

Source code:

#include "stdio.h"

void main( )
{
 int arr[5] = { 25, 17, 31, 13, 2 } ;
 int i, j, temp ;
 for ( i = 0 ; i <= 3 ; i++ )
 {
  for ( j = i + 1 ; j <= 4 ; j++ )
  {
   if ( arr[i] > arr[j] )
   {
    temp = arr[i] ;
    arr[i] = arr[j] ;
    arr[j] = temp ;
   }
  }
 }

 printf ( "\n\nArray after sorting:\n") ;

 for ( i = 0 ; i <= 4 ; i++ )
  printf ( "%d\t", arr[i] ) ;
}