Sorting algorithms
| English | Chinese | Pinyin |
|---|---|---|
| sort | 排序 | pái xù |
| bubble sort | 冒泡排序 | mào pào pái xù |
| insertion sort | 插入排序 | chā rù pái xù |
| in place | 原地 | yuán dì |
| stable | 稳定 | wěn dìng |
Putting things in order
- 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$).
An insertion sort of (D, T, H, R), shifting each key into place pass by pass
Sorting algorithms
compare adjacent, swap if needed
Step through a bubble sort: each pass floats the largest value to the end.
Bubble sort works by:
Each pass swaps adjacent pairs, "bubbling" the largest element to the end.
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.
A binary tree: each node has up to two child nodes
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.
Match each sorting idea to what it means.
Bubble swaps neighbours, insertion grows a sorted prefix; both are O(n²) worst-case; stability is about equal-key order.
Insertion sort runs close to O(n) on small or nearly-sorted arrays, because few elements need to be shifted.
On nearly-sorted data each new item is already almost in place — which is why insertion sort beats fancier sorts on small inputs.
Why sorting matters
- Sorted data enables fast binary search and easy merging.
- The cost of sorting is repaid many times over by faster later operations.
You've got it
- 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