2.3.1 - Bubble sort and insertion sort

Specify order, duplicates and storage

A sorting algorithm rearranges a collection according to a comparison rule. Ascending integers use smaller values first; a list of records might instead use a price field. Sorting must preserve the items and their multiplicities: sorting [4,2,4] gives [2,4,4], not [2,4].

All examples here use zero-based indices, comparable values and ascending order. The in-place functions change the supplied Python list and return None. Empty and one-item lists are already sorted. Python lists model the indexed collection; no built-in sorting operation is used.

Stability matters when equal keys belong to distinguishable records. If 4A preceded 4B before sorting by the number, a stable sort keeps that order. A later sort by another field can then preserve earlier ordering within ties. Bubble and insertion sort as shown are stable because they move an item past another only when its key is strictly greater. Equal keys do not cross. Stability is a property of a particular algorithm and tie rule, not of all sorting.

Auxiliary space is extra working storage beyond the input. Holding an index, flag and temporary value needs a constant number of slots, written $O(1)$, even when the input grows. Copying the whole list would instead add $O(n)$ storage. Changing the input is a separate contract decision from time complexity.

A bubble pass settles one largest item

Bubble sort compares neighbouring items from left to right and swaps an out-of-order pair. A pass is one complete sweep of the active region, not one swap. After an ascending pass, the largest active item is at the region's right end, so later passes can omit that position.

Start with [7,3,5,2]. The first pass compares (7,3), swaps to [3,7,5,2], compares (7,5), swaps to [3,5,7,2], then compares (7,2) and produces [3,5,2,7]. The next pair always uses the updated list. The 7 has moved through several pairs in the same pass.

After pass 2 the suffix [5,7] is settled. The prefix [3,2] still needs a pass. One pass cannot generally sort a list: a very small item can move only one position left in each left-to-right sweep.

An early-exit flag records whether any swap happened during the whole pass. Reset it before each pass; set it after every swap. A complete pass with no swaps proves every adjacent active pair is ordered. Together with the settled suffix, that proves the whole list is ordered. Do not stop after just one already ordered pair, and do not leave the flag set from a previous pass.

Implement shrinking passes and early exit

Safe loop bounds ensure that each comparison has both a left item and a right item. With final active index end, the left index reaches only end - 1. OCR's for ... to ... endpoint is inclusive; Python's range endpoint is excluded.

procedure bubbleSort(values, n)
    end = n - 1
    while end > 0
        swapped = false
        for i = 0 to end - 1
            if values[i] > values[i + 1] then
                temp = values[i]
                values[i] = values[i + 1]
                values[i + 1] = temp
                swapped = true
            endif
        next i
        if swapped == false then
            return
        endif
        end = end - 1
    endwhile
endprocedure

The following Python implements the same rule; simultaneous assignment safely exchanges the old values. Read and trace this example, then use the ungraded sandbox below to explore different inputs. Assessed writing uses the separate Testing editor.

def bubble_sort(values):
    for end in range(len(values) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if values[i] > values[i + 1]:
                values[i], values[i + 1] = values[i + 1], values[i]
                swapped = True
        if not swapped:
            break

data = [7, 3, 5, 2]
bubble_sort(data)
print(data)

[2, 3, 5, 7]

For an already sorted list of at least two items, one pass makes $n-1$ comparisons and exits: best-case time is $O(n)$. A reverse-ordered list needs all passes: $(n-1)+(n-2)+\cdots+1=n(n-1)/2$ comparisons, so worst-case time is $O(n^2)$. A version with fixed passes and no flag remains quadratic even on sorted input. Both versions can use $O(1)$ auxiliary space; the shown function does not copy the list.

Explore complete passes

This ungraded sandbox counts only evaluations of the adjacent greater-than test, excluding loop controls. Predict the first completed-pass list and the total comparison count, then run. Change the input to an already sorted list before comparing flag-on and flag-off versions; a faster run must still produce the required order.