Bubble sort and insertion sort

Tracing passes and insertions, counting comparisons in the best and worst case, in-place sorting and stability.

A5.4Algorithms and complexityA level25 min

At GCSE (F5.7 and F5.8) you learned how bubble sort and insertion sort work and ran them on the robot's tunes and readings. At A level you need to write them in pseudocode, trace them pass by pass, and analyse them: how many comparisons in the best and worst case, how much memory, and which data each suits.

Bubble sort

Bubble sort goes through the list comparing each pair of neighbours and swapping them if they are in the wrong order. One trip through the list is a pass. After the first pass the largest item has "bubbled" to the end; after the second, the two largest are in place, and so on. In AQA's pseudo-code, with both usual improvements:

SUBROUTINE BubbleSort(items)
    n ← LEN(items)
    pass ← 0
    swapped ← True
    WHILE swapped = True AND pass < n - 1
        swapped ← False
        FOR i ← 0 TO n - 2 - pass
            IF items[i] > items[i + 1] THEN
                temp ← items[i]
                items[i] ← items[i + 1]
                items[i + 1] ← temp
                swapped ← True
            ENDIF
        ENDFOR
        pass ← pass + 1
    ENDWHILE
ENDSUBROUTINE

The two improvements are:

1. Shrinking the pass: after pass p the last p items are already in their final places, so the inner loop stops p items earlier.
2. Stopping early: if a whole pass makes no swaps, the list is sorted and the algorithm stops.

A trace of [45, 12, 38, 7, 26, 19], showing the list after each pass:

(Bold items are in their final places.)

Analysis. In the worst case (a reversed list) every pass is needed, and the passes make (n - 1) + (n - 2) + ... + 1 comparisons. That sum is n(n - 1) / 2, which is ½n² - ½n, so bubble sort is O(n²) in the worst case. The average case is also O(n²). With the early stop, the best case is an already sorted list: one pass of n - 1 comparisons, no swaps, done, which is O(n). Without the early stop even a sorted list takes O(n²).

It swaps inside the list with one temp variable, so it is in place with O(1) extra space.

Hear the passes

Each pass is played as a short tune, so you can hear the high notes move to the end:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

tune = [523, 262, 440, 330, 392, 294]
n = len(tune)
for p in range(n - 1):
    swapped = False
    for i in range(n - 1 - p):
        if tune[i] > tune[i + 1]:
            tune[i], tune[i + 1] = tune[i + 1], tune[i]
            swapped = True
    print("after pass", p + 1, tune)
    for note in tune:
        tone(note, 0.1)
    wait(0.3)
    if not swapped:
        break

Run this in the simulator

Insertion sort

Insertion sort builds a sorted part at the front of the list. It takes the next item (the key), moves every larger item in the sorted part one place to the right, and drops the key into the gap. In OCR's Exam Reference Language:

procedure insertionSort(items)
    for i = 1 to items.length - 1
        key = items[i]
        j = i - 1
        while j >= 0 AND items[j] > key
            items[j + 1] = items[j]
            j = j - 1
        endwhile
        items[j + 1] = key
    next i
endprocedure

A trace of the same list, showing it after each key is inserted:

(Bold items are the sorted part.)

Analysis. The key for position i can be compared with up to i items, so in the worst case (a reversed list) the comparisons are 1 + 2 + ... + (n - 1) = n(n - 1) / 2, which is O(n²). On average each key moves about halfway back, roughly n²/4 comparisons, still O(n²). In the best case (already sorted) each key is compared once and stays put: n - 1 comparisons, O(n). It is in place, O(1) extra space.

Choosing between them

Both are O(n²) in the worst case and O(n) at best, so what separates them?

• Insertion sort usually does less work. Bubble sort may swap an item one place at a time across many passes; insertion sort shifts items along in one sweep. On random data insertion sort makes about half the comparisons.
• Insertion sort suits nearly sorted data: each key only moves a short way, so the work is close to O(n).
• Insertion sort can sort as data arrives. The robot can insert each new distance reading into its sorted list as it comes in. Bubble sort needs the whole list first.
• Both are stable: equal items stay in their original order (because they only move an item past a strictly larger one). That matters when sorting records by one field: runs sorted by time keep their order by date for equal times.

Neither is used on large data sets. For those you need the O(n log n) sorts in the next two lessons.

Task: count the comparisons

Write bubble_sort(items) and insertion_sort(items). Each sorts the list it is given in place, into ascending order, and returns the number of comparisons between two items it made.

• bubble_sort must use both improvements from this lesson: pass p (counting from 0) compares positions 0 and 1 up to n - 2 - p and n - 1 - p, and the sort stops after a pass with no swaps (or after n - 1 passes).
• insertion_sort counts one comparison each time it compares an item in the sorted part with the key. When j falls below 0 there is no comparison, so do not count one.

Run each sort on a copy of each of these lists (use list(...) to copy) and print six lines, bubble first, in exactly this form:

bubble ordered: 7 then bubble reversed: <n>, bubble tune: <n>, insertion ordered: <n>, insertion reversed: <n>, insertion tune: <n>

Finally sort tune with either sort and play it, each note for 0.2 seconds, lowest first.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

ordered = [262, 294, 330, 349, 392, 440, 494, 523]
reversed_notes = [523, 494, 440, 392, 349, 330, 294, 262]
tune = [392, 262, 494, 330, 523, 294, 440, 349]

def bubble_sort(items):
    return 0

def insertion_sort(items):
    return 0

Challenges

1. How many swaps does bubble sort make on the reversed list of 8? Is that also n(n - 1) / 2?
2. Rewrite bubble sort without the early stop. What is its best case now?
3. Change insertion_sort to use >= instead of >. Is it still stable? Test it on records with equal keys.