9.1 Basic Sorting: Bubble, Selection, Insertion

Chapter 9 · Basic Sorting | Prerequisites: Arrays, Loops, and Functions | Next: Shell and Merge. This page uses the same interface to compare bubble, selection, and insertion sort, focusing on movement patterns, inversions, and stability.

Three Ways to Move Elements

There are three simple methods:

• Bubble sort compares adjacent items, letting larger values bubble toward the right.
• Selection sort finds the element with the smallest key in each round and places it at the front of the unsorted section.
• Insertion sort is like organizing a deck of cards, where you insert a new card into the already sorted pile to its left.

All three have worst-case times of Θ(n²), but they work differently. First understand the process, then memorize the table.

Unified Code Contract

The following three functions accept any iterable and return a new list without modifying the input. key is computed once per element: first, each item is decorated with [sort key, original position, original value], the sorting process moves only the records, and then the original values are retrieved. Comparisons read only the sort key; the original position does not break ties and does not make selection sort stable. Input iterators are consumed, and element objects are shared by reference. Keys must have a consistent ordering, excluding unordered values such as NaN. The bounds below treat key extraction and comparison as constant-time.

The wrapper uses Θ(n) auxiliary decoration records and a separate Θ(n) output list. The "algorithm auxiliary space" in the following table counts only the sorting core; if executed directly on the caller's list, all three cores can achieve O(1) additional space.

def _decorate(values, key):
    key_function = (lambda item: item) if key is None else key
    return [
        [key_function(item), index, item]
        for index, item in enumerate(values)
    ]

def _values(records):
    return [record[2] for record in records]

def selection_sort(values, key=None):
    """Returns the result of selection sort; the standard in-place swap version is unstable."""
    records = _decorate(values, key)
    n = len(records)
    for left in range(n - 1):
        minimum = left
        for candidate in range(left + 1, n):
            if records[candidate][0] < records[minimum][0]:
                minimum = candidate
        if minimum != left:
            records[left], records[minimum] = records[minimum], records[left]
    return _values(records)

def bubble_sort(values, key=None):
    """Returns the result of a stable bubble sort with early termination."""
    records = _decorate(values, key)
    n = len(records)
    for end in range(n - 1, 0, -1):
        swapped = False
        for index in range(end):
            if records[index][0] > records[index + 1][0]:
                records[index], records[index + 1] = (
                    records[index + 1],
                    records[index],
                )
                swapped = True
        if not swapped:
            break
    return _values(records)

def insertion_sort(values, key=None):
    """Return the result of stable insertion sort."""
    records = _decorate(values, key)
    for index in range(1, len(records)):
        current = records[index]
        hole = index
        while hole > 0 and records[hole - 1][0] > current[0]:
            records[hole] = records[hole - 1]
            hole -= 1
        records[hole] = current
    return _values(records)

if __name__ == "__main__":
    data = [5, 3, 8, 1]
    print("selection:", selection_sort(data))
    print("bubble:   ", bubble_sort(data))
    print("insertion:", insertion_sort(data))
    print("original: ", data)

Run:

selection: [1, 3, 5, 8]
bubble:    [1, 3, 5, 8]
insertion: [1, 3, 5, 8]
original:  [5, 3, 8, 1]

Bubble Sort: Adjacent Swaps

Do the first round on [5, 3, 8, 1]:

[5, 3, 8, 1] compare 5 with 3 and swap
[3, 5, 8, 1] compare 5 with 8, stay put
[3, 5, 8, 1] compare 8 with 1 and swap
[3, 5, 1, 8] This round ends, and 8 has reached the final position

In the next round, only scan up to the second-to-last position, since the rightmost 8 no longer participates. If no swaps occur in a full round, swapped remains False, indicating the input is already sorted and the process can terminate.

Complexity:

• Already sorted input is checked only once, time Θ(n).
• Reverse ordering requires Θ(n²) comparisons and Θ(n²) swaps.
• Core algorithm uses O(1) auxiliary space.
• The code swaps elements only when the left key is strictly greater than the right key; equal elements retain their original order, ensuring stability.

“Bubble sort is always the slowest” isn’t a portable complexity conclusion. Actual runtime depends on implementation and input. A safer judgment is that it performs many adjacent swaps on reverse-sorted data, so application code should start with standard-library sorting unless a concrete requirement calls for something else.

Selection Sort: More scanning, fewer swaps

Trace [29, 10, 14, 37, 13]:

Initial     [29, 10, 14, 37, 13]
Round 1: smallest 10 swaps with 29 -> [10, 29, 14, 37, 13]
Round 2: swap minimum 13 with 29 -> [10, 13, 14, 37, 29]
Round 3, 14 is already in place → [10, 13, 14, 37, 29]
Round 4: smallest 29 swaps with 37 -> [10, 13, 14, 29, 37]

Regardless of the input order, the number of key comparisons is

(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2

Therefore, the best, average, and worst cases are all Θ(n²). Each outer loop iteration performs at most one swap, and the total number of swaps is at most n - 1.

Standard selection sort is unstable. Add labels to the records:

[(2, "a"), (2, "b"), (1, "x")]
In the first round, swap (1, "x") with (2, "a")
Result: [(1, "x"), (2, "b"), (2, "a")]

The order of the records with key 2 is reversed. A stability discussion must preserve record identity; looking only at [2, 2, 1] doesn't reveal this change.

Insertion Sort: Moving Out-of-Order Elements

Organize [12, 11, 13, 5, 6]:

Take 11 [11, 12, 13, 5, 6]
Take 13 [11, 12, 13, 5, 6]
Take 5   [5, 11, 12, 13, 6]
Take 6   [5, 6, 11, 12, 13]

The left side is always the sorted region. After removing current, the program shifts larger records to the right, and the resulting gap is eventually filled by current. Equal keys are not shifted, so the algorithm is stable.

The work performed by insertion sort is closely related to the inversion count I. An inversion is a pair of positions i < j for which a[i] > a[j]:

• Already sorted array I = 0, time Θ(n).
• Strictly decreasing distinct keys give I = n(n-1)/2 and Θ(n²) time.
• The number of rightward shifts of existing records is exactly I. Including each round's extraction, placement, and stopping checks gives Θ(n+I) total work.

This also explains why insertion sort is often used for small arrays or short nearly-sorted runs: it has short movement distances and simple control flow. Don't extend this to say "any nearly-sorted data should be sorted with hand-written insertion sort"; business code typically calls the language's built-in sorting instead.

What is the use of stability in real records?

Assume the list is first sorted by student ID, then by score:

[(88, "S01"), (95, "S02"), (88, "S03")]

Stable sort by score:

[(88, "S01"), (88, "S03"), (95, "S02")]

The two students scoring 88 retain their original student-ID order. The Python documentation guarantees that list.sort() and sorted() are stable, explaining how stability supports sorting on multiple keys: Python Sorting HOWTO.

Pro Quick Reference

Algorithm	Best	Average	Worst	Algorithm Auxiliary Space	Stable	Input Characteristics
Bubble (early termination)	Θ(n)	Θ(n²)	Θ(n²)	O(1)	yes	For teaching and detecting if already sorted
Selection	Θ(n²)	Θ(n²)	Θ(n²)	O(1)	No	Many comparisons; at most n-1 outer swaps
Insertion	Θ(n)	Θ(n²)	Θ(n²)	O(1)	Yes	Small scale, few inversions

The average case assumes uniformly random permutations of distinct keys. Duplicates or a different input distribution can change that average. Space in the table covers the sorting core only; the wrapper adds Θ(n) auxiliary records and a separate Θ(n) output list. Empty input returns a fresh empty list in constant time. Princeton's foundational sorting materials provide derivations and exercises for insertion, selection, and Shell sort: Elementary Sorts.

Practice Order

1. Trace all three examples on paper, circling the two positions compared at each step.
2. Add labels to the data to verify stability and instability.
3. Change > to >= and observe why bubble sort and insertion sort lose their stability.
4. Count the number of moves in insertion sort and verify it against the number of inversions.

Compare Movement and Stability

Bubble sort moves larger elements to the right through adjacent swaps; selection sorts each remaining section with at most one outer swap; insertion uses the already-sorted left portion, and the number of moves correlates directly with the number of inversions. Stability must be checked on records with identity, only comparing duplicate values cannot reveal whether the order has been reversed.

Next, let elements move farther with Shell Sort and Merge Sort.