Sorting algorithms
| English | Chinese | Pinyin |
|---|---|---|
| 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 |
The sort that is slow on purpose
- Every serious library sorts with an algorithm no exam asks you to write. Bubble sort and insertion sort are both $O(n^2)$, and both are beaten by any decent sort on a large list.
- They are on the syllabus anyway, and for a good reason: they are short enough to trace by hand, and tracing one is how you learn what a sort actually does to an array.
- There is also a real case for insertion sort. On a list that is small, or already nearly sorted, it is genuinely the fastest thing there is, and real libraries switch to it for exactly those cases.
- This lesson is bubble sort 冒泡排序 and insertion sort 插入排序: the algorithms, their behaviour, and where each one wins.
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
ENDIF
NEXT i
IF NOT swapped THEN EXIT FOR // already sorted
NEXT pass
- Each pass compares adjacent pairs and swaps any that are out of order, so the largest remaining value "bubbles" to the end.
- After pass $k$ the last $k$ elements are final, which is why the inner loop stops at $n - \text{pass}$.
- The
swappedflag lets it stop early: if a whole pass makes no swap, the list is sorted.
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] // shift right
j ← j - 1
ENDWHILE
A[j + 1] ← key // drop it in
NEXT i
- It builds a sorted section at the front, growing by one each time. Each new element is held aside as
key, larger elements are shifted right to open a gap, and the key is dropped in. - This is how most people sort a hand of playing cards, which is the analogy the exam expects.
The left is sorted, the right is untouched, and the boundary moves right
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.
Worked example: trace one pass
- Trace the first pass of a bubble sort on 5, 3, 8, 1.
- Compare 5 and 3: out of order, swap, giving 3, 5, 8, 1. Compare 5 and 8: in order, no swap. Compare 8 and 1: swap, giving 3, 5, 1, 8.
- After one pass the largest value, 8, is in its final position, and one more comparison per pass can be skipped from now on.
- Now trace insertion sort's third step on 3, 5, 8, 1. The key is 1. Shift 8, 5 and 3 each one place right, then place 1 at the front: 1, 3, 5, 8. Show the array after every step; that is where the marks are.
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.
How does insertion sort place each new element?
Holding the key aside and shifting is what distinguishes it from bubble sort's repeated adjacent swaps.
Performance
| bubble | insertion | |
|---|---|---|
| best case | $O(n)$, one pass with no swaps | $O(n)$, already sorted, no shifts |
| average and worst | $O(n^2)$ | $O(n^2)$ |
| extra memory | $O(1)$, in place 原地 | $O(1)$, in place |
| stable | yes | yes, stable 稳定 |
- In place means it needs only a constant amount of extra memory, sorting within the array itself. Stable means two equal values keep their original relative order, which matters when a list has already been sorted by another field.
- Both reach $O(n)$ on already-sorted data, but only if bubble sort has the
swappedflag. Without it, it always performs every pass.
After the first pass of a bubble sort on 5, 3, 8, 1, what is the array? Write the four numbers separated by commas.
5 and 3 swap, 5 and 8 do not, 8 and 1 swap. The largest value has reached the end, so the next pass can be one comparison shorter.
Worked example: which sort, and why
- A list of 200,000 records must be sorted from scratch. Neither: both are $O(n^2)$, so a merge or quick sort at $O(n \log n)$ is needed. Say so rather than choosing the least bad.
- A sorted list of 10,000 gains 5 new records at the end and must be sorted again. Insertion sort: the data is nearly sorted, so each new key shifts only a short distance and it approaches $O(n)$.
- A teaching example must be traced by hand on paper. Bubble sort: it is the simplest to follow, which is its real remaining use.
- Justify from the state of the data and the size, not from a general preference.
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.
Which are true of both bubble sort and insertion sort? Select all that apply.
On a large unsorted list an O(n log n) sort wins decisively. Saying so is the right answer, not choosing the least bad of the two.
Why one pass is not the whole story
- Both sorts do repeated passes, and the exam distinguishes them by what one pass achieves and by when they stop.
- A bubble sort pass compares adjacent pairs and swaps them, so one pass carries the largest remaining item to its final place. The whole sort is $n - 1$ passes.
- An insertion sort pass takes the next item and moves it back into the already-sorted part, so after $k$ passes the first $k$ items are sorted among themselves but not yet in final position.
- Bubble sort can be improved with a flag: if a pass makes no swaps, the list is already sorted and the algorithm stops. On nearly-sorted data that turns it into one pass.
- Without the flag, both are $n^2$ in the worst case, which is why either is a poor choice for a large file and why the exam asks about small ones.
A sorted list of 10,000 records gains 5 new records at the end. Which sort suits re-sorting it?
Nearly sorted data is exactly insertion sort's best case, approaching O(n). Real libraries switch to it for this reason.
Match each sort to what one pass achieves.
That difference is what a trace question is really testing. A bubble-sort flag also lets it stop early on nearly-sorted data, which insertion sort handles well anyway.
Marks that slip away
- Bubble sort compares adjacent pairs. An answer that compares an element with all the others is describing a different algorithm.
- The inner loop shortens each pass, because the end of the array is already final. Say why.
- Insertion sort shifts elements right to open a gap; it does not swap repeatedly. The distinction is the point of the algorithm.
- Both are $O(n^2)$ on average and at worst, and $O(n)$ at best. Give the case with the order.
You've got it
- bubble sort: repeated passes comparing adjacent pairs and swapping, largest bubbling to the end, inner loop shortening each pass, with a
swappedflag for early exit - insertion sort: grow a sorted section at the front, holding each key aside, shifting larger elements right and dropping the key into the gap
- both are $O(n^2)$ average and worst, $O(n)$ best, in place and stable
- insertion sort genuinely wins on small or nearly sorted lists; for a large unsorted list neither is the right answer