Sorting |
|
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..i-1] sorted and elements a[1..i-1] <= 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..j-1] */ 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..N-1] sorted and elements a[1..N-1] <= a[N] */ /* i.e. a[1..N] sorted. */ }/*selection*/ At some intermediate stage, a[1..i-1] 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=N-1. Selection Sort DemonstrationTry other example input in the HTML FORM below, press `go' and experiment. ComplexityTimeThe number of comparisons of elements is (N-1) + (N-2) + ... + 1 = (N-1)*N/2i.e. O(N2). SpaceThe space-complexity 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 [2a,2b,1]. (Thanks to Giri Narasimhan 6/4/'05.) TestingTest sort programs on a few special cases:
Notes
L. A. © Dept. Computer Science, University of W.A. 1984. |
|
|