Sorting 

There are many sorting algorithms with just a few listed on the left. Sorting is an important problem that is easily understood and has interesting, mostly short solutions. Selection sort is one of the simpler algorithms. Selection SortSelection sort maintains a growing 'front' section of the array which is (i) sorted and (ii) less than the remainder of the array. At each step, the smallest element in the 'remainder' is selected and moved to enlarge the 'front' section. selection(int a[], int N) /* in C */ /* sort a[1..N], NB. 1 to N */ { int i, j, smallest, aSmallest, temp; for(i=1; i < N; i++) { /* invariant: a[1..i1] sorted and elements a[1..i1] <= a[i..N] */ smallest = i; /* find smallest in a[i..N] */ aSmallest = a[i]; for(j=i+1; j <= N; j++) /* a[smallest] is the least element in a[i..j1] */ if(a[j] < aSmallest) { smallest=j; aSmallest=a[j]; } /* a[smallest] is the least element in a[i..j] */ temp=a[i]; a[i]=a[smallest]; a[smallest]=temp; /*swap*/ /* a[1..i] sorted and elements a[1..i] <= a[i+1..N] */ } /* a[1..N1] sorted and elements a[1..N1] <= a[N] */ /* i.e. a[1..N] sorted. */ }/*selection*/ At some intermediate stage, a[1..i1] is sorted and, on an element by element basis, less than everything in a[i..N]. Find the smallest element remaining in a[i..N]:
Do this by examining a[i], a[i+1], ..., a[N]:
Swap a[i] with a[smallest]:
Now a[1..i] is sorted and less than everything remaining in a[i+1..N]. (Coincidentally a[1..N] happens to be sorted in this example.) Repeat until i=N1. Selection Sort DemonstrationTry other example input in the HTML FORM below, press 'go' and experiment. ComplexityTimeThe number of comparisons of elements is (N1) + (N2) + ... + 1 = (N1)*N/2i.e. O(N^{2}). SpaceThe spacecomplexity is O(1), just a few scalar variables.
StabilitySelection sort is not stable, the is the relative order of equal keys is sometimes changed. It is the swap that can do it, consider [2_{a},2_{b},1]. (Thanks to Giri Narasimhan 6/4/'05.) TestingTest sort programs on a few special cases:
Notes
L. A. ©


