Selection sort works by repeatedly scanning the unsorted portion of a list, finding the smallest remaining value, and swapping it into its correct position. After each pass one more item is permanently placed, so with a list of n items the algorithm always makes exactly n − 1 passes.
How does the selection sort algorithm work?
Think of selection sort as a student arranging a hand of playing cards face down. They flip every card to find the lowest value, move it to the leftmost position, then flip all remaining cards to find the next lowest, and so on. Each round of searching the whole remaining deck is one "pass".
Algorithm in plain steps:
- Start with the whole list unsorted.
- Find the position of the minimum value in the unsorted section.
- Swap that minimum value with the first element of the unsorted section.
- The sorted section grows by one element.
- Repeat from step 2 for the remaining unsorted section.
- Stop when the unsorted section has only one element — it must already be in the correct position.
Worked example — trace selection sort on [6, 2, 8, 3, 1]
Pass 1 — find minimum in [6, 2, 8, 3, 1], which is 1 (at index 4). Swap with index 0.
| Before | Action | After |
|---|---|---|
| [6, 2, 8, 3, 1] | Swap 6 and 1 | [1, 2, 8, 3, 6] |
Sorted so far: [1]
Pass 2 — find minimum in [2, 8, 3, 6], which is 2 (already at index 1). No swap needed.
| Before | Action | After |
|---|---|---|
| [1, 2, 8, 3, 6] | Already in position | [1, 2, 8, 3, 6] |
Sorted so far: [1, 2]
Pass 3 — find minimum in [8, 3, 6], which is 3 (at index 3 overall, index 1 within unsorted). Swap with 8.
| Before | Action | After |
|---|---|---|
| [1, 2, 8, 3, 6] | Swap 8 and 3 | [1, 2, 3, 8, 6] |
Sorted so far: [1, 2, 3]
Pass 4 — find minimum in [8, 6], which is 6 (at index 4 overall). Swap with 8.
| Before | Action | After |
|---|---|---|
| [1, 2, 3, 8, 6] | Swap 8 and 6 | [1, 2, 3, 6, 8] |
Sorted so far: [1, 2, 3, 6]
Pass 5 — only one element remains: [8]. Already in correct position.
Final sorted list: [1, 2, 3, 6, 8] ✓
How many comparisons does selection sort make?
For a list of n elements:
- Pass 1 scans n − 1 pairs to find the minimum.
- Pass 2 scans n − 2 pairs.
- Pass 3 scans n − 3 pairs.
- …
- Pass n − 1 scans 1 pair.
Total comparisons = (n − 1) + (n − 2) + … + 1 = n(n − 1) / 2
For n = 5: 4 + 3 + 2 + 1 = 10 comparisons
This grows as n², so the Big O notation for selection sort is O(n²) in all cases — best, average, and worst. Unlike bubble sort, selection sort cannot terminate early if the list is already sorted, because it has no way to detect this without scanning.
How many swaps does selection sort make?
Selection sort makes at most n − 1 swaps — exactly one per pass (or zero if the minimum is already in position). This is an important practical advantage. Bubble sort can make O(n²) swaps in the worst case; selection sort never exceeds n − 1 swaps regardless of input order. This matters when swapping is expensive — for example, when elements are large records stored on a slow disk.
How does selection sort compare with other sorting algorithms?
| Feature | Selection sort | Bubble sort | Merge sort |
|---|---|---|---|
| Comparisons (worst case) | O(n²) | O(n²) | O(n log n) |
| Swaps (worst case) | O(n) | O(n²) | O(n log n) |
| Can exit early if sorted? | No | Yes (optimised) | No |
| Extra memory needed? | In-place (O(1)) | In-place (O(1)) | O(n) extra |
| Stable? | No (swaps can change relative order) | Yes | Yes |
Selection sort is not stable: swapping the current first element with a distant minimum can move equal-value elements past each other, changing their relative order.
How do you write selection sort in pseudocode?
FOR i ← 0 TO length(list) - 2
minIndex ← i
FOR j ← i + 1 TO length(list) - 1
IF list[j] < list[minIndex] THEN
minIndex ← j
END IF
END FOR
IF minIndex ≠ i THEN
temp ← list[i]
list[i] ← list[minIndex]
list[minIndex] ← temp
END IF
END FOR
The outer loop advances the boundary between the sorted and unsorted sections. The inner loop scans the unsorted section to find the minimum. The swap uses a temporary variable temp — the standard three-line swap pattern you should know by heart.
Frequently asked questions
Is selection sort on the AQA and OCR GCSE specifications?
Selection sort is listed in the AQA GCSE Computer Science specification alongside bubble sort and merge sort. OCR also includes it. You should be able to trace the algorithm on a given list, describe how it works in words or pseudocode, state its complexity (O(n²) comparisons), and compare it with bubble sort and merge sort. Check your specific exam board's specification for the exact requirement.
Why does selection sort always make O(n²) comparisons even for a sorted list?
Because the algorithm scans the entire unsorted section to find the minimum on every pass, it cannot detect that the list is already sorted. On pass 1 it makes n − 1 comparisons regardless. There is no optimisation equivalent to bubble sort's "stop if no swaps occurred". This predictability can be an advantage in some contexts: the running time never varies based on the input.
What is meant by an in-place sorting algorithm?
An in-place algorithm sorts the data using only a small, constant amount of additional memory — typically just one or two temporary variables. Selection sort is in-place because it rearranges elements within the original list using a single temp variable for swapping. Merge sort is not in-place because it creates new sub-lists during the merge phase, requiring additional memory proportional to the list size.
How do you choose between selection sort and bubble sort for an exam answer?
For a nearly sorted list, prefer bubble sort (with the optimisation): it can terminate in O(n) time if it completes a full pass with no swaps. For a list where swapping is expensive, prefer selection sort: it performs at most n − 1 swaps regardless of input order. For large, unsorted lists where speed is critical, prefer merge sort with its O(n log n) performance. Exam questions may ask you to justify a choice — state the specific characteristic that makes your chosen algorithm more suitable.
Trace sorting algorithms and practise pseudocode with Professor Turing's step-by-step feedback at aitutors.me.