Lesson 16
Bubble, Selection & Insertion Sort
Three O(n²) sorts — and why insertion sort still ships in production.
01Why it matters & the intuition
Simple sorts teach comparisons, swaps, stability and invariants. Insertion sort is also genuinely used: fast libraries switch to it for small or nearly-sorted chunks.
Think of it like…
Sorting a hand of playing cards: you pick up one card at a time and slide it left until it sits in the right place. That is insertion sort. Bubble sort repeatedly swaps neighbours so big cards 'bubble' right; selection sort repeatedly picks the smallest remaining card.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- comparing / current
- moving / removing
- done / found / visited
- pivot / min / root
03Key ideas
Bubble sort
Swap adjacent out-of-order pairs; after pass k the largest k items are in place. Stop early if a pass makes no swaps.
Selection sort
Find the minimum of the unsorted part and swap it to the front. Always n²/2 comparisons, but at most n swaps.
Insertion sort
Grow a sorted prefix; shift larger items right to make room for the next item. O(n) on already-sorted input.
Stability
A stable sort keeps equal items in their original order. Bubble and insertion are stable; selection is not.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
function bubbleSort(a: number[]): number[] {
for (let end = a.length - 1; end > 0; end--) {
let swapped = false;
for (let i = 0; i < end; i++) {
if (a[i] > a[i + 1]) { [a[i], a[i + 1]] = [a[i + 1], a[i]]; swapped = true; }
}
if (!swapped) break; // already sorted
}
return a;
}
function selectionSort(a: number[]): number[] {
for (let i = 0; i < a.length - 1; i++) {
let min = i;
for (let j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j;
if (min !== i) [a[i], a[min]] = [a[min], a[i]];
}
return a;
}
function insertionSort(a: number[]): number[] {
for (let i = 1; i < a.length; i++) {
const key = a[i];
let j = i - 1;
while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } // shift right
a[j + 1] = key;
}
return a;
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Bubble sort | O(n²) · best O(n) | O(1) |
| Selection sort | O(n²) always | O(1) |
| Insertion sort | O(n²) · best O(n) | O(1) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Implement insertion sort
Write insertion_sort(arr) that sorts numbers ascending in place and returns the array. Do not call .sort().