Selection Sort
Find the smallest remaining item and swap it to the front. Repeat. Simple, at most n − 1 swaps, but always O(n²) comparisons.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
You’re picking a football team, best player first. You look at everyone still available, pick the best, and they step forward. Then you look at everyone remaining again… That is selection sort, except we pick the smallest each time.
The idea
The array has two parts: a sorted part on the left (initially empty) and an unsorted part on the right.
- Scan the unsorted part to find the minimum.
- Swap it with the first unsorted item. The sorted part grows by one.
- Repeat n − 1 times.
Why it’s always O(n²)
To be sure an item is the minimum, you must look at every remaining item. Pass 1 makes n − 1 comparisons, pass 2 makes n − 2, and so on:
That happens no matter what the input is, even if it’s already sorted.
Its one strength
It does at most n − 1 swaps. If moving data is very expensive (huge records, flash memory), that matters. For huge records, see pointer sort next.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Watch the swaps counter. It never goes above n − 1.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <utility>
using namespace std;
void selectionSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[minIdx])
minIdx = j;
swap(a[i], a[minIdx]); // at most one swap per pass
}
}
int main() {
int a[] = {29, 10, 14, 37, 13, 5};
int n = sizeof(a) / sizeof(a[0]);
selectionSort(a, n);
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << "\n";
}5 10 13 14 29 37
05Complexity
| Best case | O(n²): it still scans for the minimum every pass |
|---|---|
| Average case | O(n²) |
| Worst case | O(n²): n(n−1)/2 comparisons |
| Swaps | at most n − 1 (the fewest of the simple sorts) |
| Extra space | O(1) |
| Stable? | No |
| In-place? | Yes |
Good when writing to memory is expensive (few swaps). Bad when the data is already nearly sorted, because it cannot stop early.
06Watch
Selection sort algorithm
Why this one: Derives the algorithm from the "find the minimum" idea and analyses it carefully.
Selection sort in 3 minutes
Why this one: A 3-minute animation. Ideal as a pre-exam refresher.
Original class slides (Python, by the course's lecture authors):Sorting Basics
07Exam lens
Likely questions
- Trace selection sort on
64, 25, 12, 22, 11, showing the array after each pass. - How many comparisons and swaps does selection sort make for n items?
- Why is selection sort not stable? Give an example.
- Compare selection sort and bubble sort in terms of swaps.
Common mistakes
- Swapping inside the inner loop every time a smaller item is found. Swap once, after the inner loop.
- Starting the inner loop at
j = iinstead ofj = i + 1(compares an item with itself). - Claiming selection sort has an O(n) best case. It has none; it always scans.
08Quick check
09Practice
🟢 Trace by hand
Trace selection sort on 64, 25, 12, 22, 11. Show the array after each pass and count comparisons.
Show answer
- Pass 1: min 11 →
11 25 12 22 64 - Pass 2: min 12 →
11 12 25 22 64 - Pass 3: min 22 →
11 12 22 25 64 - Pass 4: min 25 →
11 12 22 25 64
Comparisons: 4 + 3 + 2 + 1 = 10 = 5·4/2.
🟡 Implement it
Write selectionSortMax that sorts ascending by repeatedly finding the maximum and placing it at the end.
Hint
Outer loop: for (int end = n - 1; end > 0; end--). Inner loop finds the index of the max in [0..end].
Solution
void selectionSortMax(int a[], int n) {
for (int end = n - 1; end > 0; end--) {
int maxIdx = 0;
for (int j = 1; j <= end; j++)
if (a[j] > a[maxIdx]) maxIdx = j;
swap(a[maxIdx], a[end]);
}
}🔴 Solve problems
Hint
Selection sort works (n ≤ 300). Then try the one-pass "Dutch national flag" approach with three pointers.
Hint
Copy the array, sort the copy with your own selection sort, then count positions that differ.
Hint
This is three passes of "find the max", the core step of selection sort. Watch out for duplicates.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.