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
editIn 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^{2} * 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^{2} * D + n * E - n
- T_{sort} = n^{2} * D + n * (E – 1)
- T_{sort} = n^{2} * 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
editWe 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 |