ソートアルゴリズム

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      // already sorted
        EXIT FOR
    ENDIF
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 swapped flag 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

Worked example: trace one pass

Performance

• 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 swapped flag. Without it, it always performs every pass.

Worked example: which sort, and why

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.

Marks that slip away

You've got it