## 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 Sort

Selection 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]:

select smallest ------- a: 1 2 3 6 5 4 ------- ^ sorted | & small | i

Do this by examining a[i], a[i+1], ..., a[N]:

a: 1 2 3 6 5 4 ^ ^ | | i smallest

Swap a[i] with a[smallest]:

a: 1 2 3 4 5 6 ---------- sorted ^ & small | | i

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 Demonstration

Try other example input in the HTML FORM below, press 'go' and experiment.

### Complexity

#### Time

The number of comparisons of elements is

(N-1) + (N-2) + ... + 1 = (N-1)*N/2i.e. O(N

^{2}).

#### Space

The space-complexity is O(1), just a few scalar variables.
**NB**. We do not count the size of the array being
sorted because that is given, not created specifically for this algorithm.

### Stability

Selection 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.)

### Testing

Test sort programs on a few special cases:

- the empty array!
- an array of a single element,
- an array of a small number of elements,
- some already sorted data,
- some reverse sorted data,
- some random data (several sets),
- data with duplicate keys.

### Notes

- Depending on your language, you may find yourself sorting a[1..N] or a[0..N-1]; watch those indices!