Selection sort repeatedly finds the smallest value in the unsorted section of a list and swaps it with the first value in that section. After each pass, one more value is in its correct final position.
The Selection Sort Mechanism
For an array sorted in ascending order:
- Treat the entire array as unsorted.
- Search the unsorted section for its minimum value.
- Swap that minimum with the first value in the unsorted section.
- Move the boundary of the sorted section one position to the right.
- Repeat until only one unsorted value remains.
For example, sort [7, 3, 5, 2]:
| Pass | Operation and resulting array |
|---|---|
| 1 | Minimum is 2; swap with 7 to produce [2, 3, 5, 7] |
| 2 | Minimum of [3, 5, 7] is already 3; no effective change |
| 3 | Minimum of [5, 7] is already 5; sorting is complete |
A typical selection sort algorithm is:
FOR position FROM 0 TO length(array) - 2
minimumIndex = position
FOR index FROM position + 1 TO length(array) - 1
IF array[index] < array[minimumIndex]
minimumIndex = index
END IF
END FOR
SWAP array[position] WITH array[minimumIndex]
END FOR
The nested loops make approximately comparisons, so selection sort has time complexity in its best, average, and worst cases. It sorts in place, requiring only additional space.
A common misconception is that selection sort swaps values whenever it finds a smaller one. Instead, it records the index of the smallest value during a pass and normally performs one swap after the search.
IB Exam Technique
For B2.4 programming algorithms, be ready to trace the array after each complete pass, explain the roles of the sorted and unsorted sections, or construct pseudocode. When discussing efficiency, state both the complexity and its cause: the algorithm repeatedly searches the remaining unsorted values using nested loops.
