Sorting algorithms
Sorting algorithms
- A sort puts a collection into order.
- Two simple ones: bubble sort and insertion sort.
- Both are easy to code but slow ($O(n^2)$) on large lists.
Bubble sort
FOR pass ← 1 TO n - 1
swapped ← FALSE
FOR i ← 1 TO n - pass
IF A[i] > A[i + 1] THEN
swap A[i], A[i + 1]
swapped ← TRUE
NEXT i
IF NOT swapped THEN EXIT FOR // already sorted
NEXT pass
- Repeatedly swaps adjacent out-of-order pairs, so the largest "bubbles" to the end each pass.
- Best case O($n$) (already sorted, early exit); average/worst O($n^2$).
Practice
Bubble sort works by:
Each pass swaps adjacent pairs, "bubbling" the largest element to the end.
Practice
The average/worst-case time complexity of bubble sort is:
Two nested loops over n elements give O(n²); the best case (already sorted) is O(n) with the early exit.
Insertion sort
FOR i ← 2 TO n
key ← A[i]
j ← i - 1
WHILE j >= 1 AND A[j] > key DO
A[j + 1] ← A[j]
j ← j - 1
ENDWHILE
A[j + 1] ← key
NEXT i
- Builds a sorted prefix from the left, inserting each new element by shifting larger ones right.
- Best O($n$), worst O($n^2$); sorts in place and is stable. Great for small or nearly-sorted arrays.
Practice
Insertion sort builds the sorted result by:
It grows a sorted prefix on the left, shifting larger elements right to drop each key into place.
Practice
Insertion sort is especially good for:
On nearly-sorted data few shifts are needed, so it runs close to O(n).
Practice
A "stable" sort:
Stability means two equal-valued items stay in the same order they started in.
You've got it
Key idea
- bubble sort: swap adjacent pairs each pass; largest bubbles to the end; O($n^2$)
- insertion sort: build a sorted prefix, shifting larger elements right; O($n^2$), in place + stable
- both are O($n$) on already-sorted data (with early exit / no shifts)
- insertion sort is good for small or nearly-sorted lists