SelectionSort

SelectionSort divides a list into a sorted part and the unsorted part. At the beginning everything belongs to the unsorted part. Then the element with the smallest key value is looked up and swaped with the first element of the list. The sorted part now starts and ends with element 1 and the unsorted part starts with element 2. In the second run the smallest element is looked up starting from position 2. When the smallest element is determined it swaps with the element on position two. If the comparison is done with "smaller" and not "smaller or equal", the algorithm works stable. And, what should be obvious, it works in place.

Timing

In order to calculate the number of compare operations we use a visualization. In the first run the first element is compared with all others to find the smallest; this results in n - 1 compares. In the second run element two is compared with all others which results in n – 2 compares and so on. For 10 records we get the compare matrix:

      1   2   3   4   5   6   7   8   9  10
 1    -   x   x   x   x   x   x   x   x   x    n – 1
 2    -   -   x   x   x   x   x   x   x   x    n – 2
 3    -   -   -   x   x   x   x   x   x   x    n - 3
 4    -   -   -   -   x   x   x   x   x   x    n - 4
 5    -   -   -   -   -   x   x   x   x   x    n - 5
 6    -   -   -   -   -   -   x   x   x   x    n - 6
 7    -   -   -   -   -   -   -   x   x   x    n - 7
 8    -   -   -   -   -   -   -   -   x   x    n - 8
 9    -   -   -   -   -   -   -   -   -   x    n - 9
 10   -   -   -   -   -   -   -   -   -   -    n – 10

The n * n matrix is half filled except for the diagonal which is n elements long. This gives the time for comparing with

T_cmp = ½ n² * C - n

SelectionSort needs in maximum one swap operation per data record (sometimes the smallest element is already on the target position)

T_swp = n * E

The total time for a sort can be estimated by

T_sort = T_cmp + T_swp

T_sort = n² * D + n * E - n

T_sort = n² * D + n * (E – 1)

T_sort = n² * D + n * F

with D = ½ C and E and F = E – 1 being constants.

Even when the costs for swapping are low and D is small, the quadratic term will increase for bigger record numbers very fast and the fact that for swapping the necessary time only increases in linear fashion does not play any important role then.

In a concrete situation it could be vital that SelectionSort is about twice as fast as InsertionSort, but if there are algorithms available with better characteristics it is still a bad choice when there are more than a few dozens of records to be sorted.

In a situation where the records are nearly sorted, the time for swaps will be near to zero, but the number of compare operations still increases in a quadratic manner.

Example

We start with this input list; the background is blue where the smalles element goes and the smallest element to be found has a green background:

387	310	529	174	011	227	020	901	522	771
011	310	529	174	387	227	020	901	522	771
011	020	529	174	387	227	310	901	522	771
011	020	174	529	387	227	310	901	522	771
011	020	174	227	387	529	310	901	522	771
011	020	174	227	310	529	387	901	522	771
011	020	174	227	310	387	529	901	522	771
011	020	174	227	310	387	522	901	529	771
011	020	174	227	310	387	522	529	901	771
011	020	174	227	310	387	522	529	771	901