3.9.2 Selection Sort

Knowledge Base > Algorithm > Sorting

Overview

As its name suggest, Selection sort works by selecting elements in specific order, and putting them in proper position in the final list. Selection sort is an in-place sorting algorithm, which requires O(1) of space to swap. Similar to other elementary sorting methods, selection sort runs at O(n²) complexity, making it very inefficient on huge lists.

Algorithm

Pseudocode

Selection-Sort(A)

1 for i ← 1 to length[A] - 1 2 do min ← i 3       for j ← i + 1 to length[A] 4       do if A[j] < A[min] 5                then min = j 6       swap A[i] with A[min]

Assume the list is to be sorted in ascending order. The idea of selection sort is as simple as follow:

• Linear-search for the minimum remaining element in the unsorted portion of the list.
• Exchange with the element of the corresponding position in sorting order. That is,
• Repeat those two steps for the rest of the list.

Loop Invariant of Inner Loop
Statement
Before the start of the j^th iteration, min contains the index of the smallest element among A[i…j - 1]
Initialization
Before the start of the 1^st iteration, j = i + 1, min contains the index of the smallest element among A[i…i], which is the first index of A.⇒ True.
Maintenance
Before the start of the j^th iteration, min contains the index of the smallest element among A[i…j - 1] After running line 4 and 5, let min equals to j, if A[j] < A[min], min now stores the index of the smallest element in array A[i…j].
Termination
Before the start of the n + 1^th iteration, j = n + 1, min contains the index of the smallest element among A[i…n]

Loop Invariant of Outer Loop
Statement
Before the start of the i^th iteration, A[1…i - 1] stores the first (i - 1) smallest elements in A in sorted order.
Initialization
Before the start of the 1^st iteration, i = 1, A[1…0] stores the first 0 smallest element in A in sorted order.⇒ Trivially True.
Maintenance
Before the start of the i^th iteration, A[1…i - 1] stores the first (i - 1) smallest elements in A in sorted order. From the last inner-loop-loop-invariant, we know that A[min] will hold the smallest value in array [i…n]. So, after running through the inner loop, A[1…i] stores the first i smallest elements in A in sorted order.
Termination
Before the start of the n^th iteration, i = n, A[1…n - 1] stores the first (n - 1) smallest elements in A in sorted order. This implies that A[n] is the biggest in array A. Hence, the whole array is sorted.

Thus, prove the correctness of Selection-Sort.

Time Complexity

In the first round, it requires scanning all n elements, taking n- 1 comparisons, and swapping it into the first position. Next, finding the next lowest element requires scanning the remaining n - 1 elements and making n - 2 comparisons and perform the swap. Thus, a total T(n) = (n - 1) + (n - 2) + ... + 2 + 1 = = Θ(n²) of comparisons and n swaps have been done after the list is sorted. Thus, the selection sort always performs Θ(n²) of running time. However, one disadvantage is that the running time of selection sort barely depends on the amount of order already in file. That is, it takes as long running time to run selection sort on a list that is already sorted, or a list of duplicated keys, as it takes for a list of distinct random values.

Space Complexity

This is an in-place algorithm, which means no more than constant space is required to perform the operation. Thus, the space complexity is O(1).

Stability

Selection sort is not stable, because the order of occurrence of the same key is hard to maintain after swap. However, there is a way to implement selection sort into a stable sort: replacing swap with insertion operation. That is, all other elements moved down by one index after insertion is performed. Then, the algorithm is stable, but with greater overhead of Θ(n²) writes to memory. This change eliminates the main advantage of selection sort over insertion sort, which is always stable.

In Practice

Despite of the innate evident brute-force approach, selection sort sometimes outperforms in sophisticated applications. such as sorting a relatively small list of huge data structure. This implies that the cost of moving the data dominates the cost of performing comparisons [2], and selection sort is one of the sorting method that performs less data movement during the play.

Source Code

• Selection Sort (C)