Bubble, Selection, and Insertion Sort

Binary search assumed sortedness; so sorting itself must now be examined. Sorting stands at the center of algorithm education: the same problem has been solved dozens of times with different ideas, and the solutions have been compared with exactly the tools of this course.

This lesson covers three basic algorithms with quadratic cost. The goal is not only to learn them, but to establish a baseline against which the better algorithms of the following lessons will be compared.

The Problem and Its Criteria

The sorting problem: The input is an array of comparable elements. The output is an array that is a permutation of the same elements, arranged in non-decreasing order.

Both conditions are required. If only orderedness were demanded, deleting the input and returning an empty array would count as a “solution”; the permutation condition rules this out.

Sorting algorithms are distinguished by three criteria:

Stability. An algorithm is stable if it preserves the relative order of elements with equal keys. This is decisive in multi-key sorting: records first sorted by city, then by date with a stable algorithm, keep the city order intact.

In-place operation. An algorithm is in-place if its extra space is constant.

Adaptivity. An algorithm is adaptive if its cost drops when the input is partially sorted.

Two separate costs are also counted: the number of comparisons and the number of moves (swaps or shifts). If the elements are large objects, moves are expensive; if comparison is a complex function, comparisons are expensive.

Bubble Sort

Adjacent elements are compared and swapped if out of order. On every pass, the largest element “bubbles” to the end.

def bubble_sort(array: list[int]) -> list[int]:
    """Invariant: after every outer iteration, the last `n - last` elements are in their final position."""
    d = list(array)
    for last in range(len(d) - 1, 0, -1):
        swapped = False
        for i in range(last):
            if d[i] > d[i + 1]:
                d[i], d[i + 1] = d[i + 1], d[i]
                swapped = True
        if not swapped:                 # if no swap occurred, the array is sorted
            break
    return d


print(bubble_sort([5, 2, 9, 1, 5, 6]))    # [1, 2, 5, 5, 6, 9]

Without the early-exit flag, the algorithm makes $n(n-1)/2$ comparisons in every case. With the flag, it stops in a single pass on sorted input: the best case becomes $O(n)$.

The worst and average cases are $O(n^2)$. The number of moves can also be quadratic — on reverse-sorted input, every comparison leads to a swap. The algorithm is stable (elements swap only when strictly out of order) and in-place.

Selection Sort

The minimum of the remaining segment is found, and it is swapped with the element at the start of the boundary.

def selection_sort(array: list[int]) -> list[int]:
    """Invariant: after every iteration, the first i elements are finally sorted."""
    d = list(array)
    for i in range(len(d) - 1):
        smallest = i
        for j in range(i + 1, len(d)):
            if d[j] < d[smallest]:
                smallest = j
        d[i], d[smallest] = d[smallest], d[i]
    return d


print(selection_sort([5, 2, 9, 1, 5, 6]))     # [1, 2, 5, 5, 6, 9]

The number of comparisons is independent of the input: always $n(n-1)/2$. It is not adaptive — it pays the full cost even on sorted input.

In exchange, the number of moves is at most $n-1$, and this is the algorithm’s sole advantage: if elements are very large, or if writing is expensive (in some persistent storage types, the cost of reading and writing is unequal), an algorithm that writes little may be preferred.

In this form it is not stable: swapping with a distant element can disturb the order of equal keys.

def selection_sort_records(records: list[tuple[int, str]]) -> list[tuple[int, str]]:
    """Sorts by the first field (the key) only; the second field is an identity."""
    d = list(records)
    for i in range(len(d) - 1):
        smallest = i
        for j in range(i + 1, len(d)):
            if d[j][0] < d[smallest][0]:
                smallest = j
        d[i], d[smallest] = d[smallest], d[i]
    return d


print(selection_sort_records([(2, "a"), (2, "b"), (1, "c")]))
# [(1, 'c'), (2, 'b'), (2, 'a')]

In the output, b has moved ahead of a; in the input the order was reversed. A variant that shifts instead of swapping would be stable, but then the move advantage is lost.

Insertion Sort

Every element is inserted by shifting it to its correct place within the sorted segment before it. This is the way playing cards are sorted by hand.

def insertion_sort(array: list[int]) -> list[int]:
    """Invariant: at the start of every iteration, the first i elements are sorted among themselves."""
    d = list(array)
    for i in range(1, len(d)):
        key = d[i]
        j = i - 1
        while j >= 0 and d[j] > key:
            d[j + 1] = d[j]             # shift
            j -= 1
        d[j + 1] = key
    return d


def insertion_sort_records(records: list[tuple[int, str]]) -> list[tuple[int, str]]:
    d = list(records)
    for i in range(1, len(d)):
        key = d[i]
        j = i - 1
        while j >= 0 and d[j][0] > key[0]:
            d[j + 1] = d[j]
            j -= 1
        d[j + 1] = key
    return d


print(insertion_sort([5, 2, 9, 1, 5, 6]))    # [1, 2, 5, 5, 6, 9]
print(insertion_sort_records([(2, "a"), (2, "b"), (1, "c")]))
# [(1, 'c'), (2, 'a'), (2, 'b')]   — the a, b order from the input is preserved

The > sign in the loop condition is the source of stability: on equality, shifting stops, and the new element settles right after its equal. Writing >= would make the algorithm lose its stability.

The best case is sorted input: the inner loop never runs, cost is $O(n)$. The worst case is reverse-sorted input: $n(n-1)/2$ shifts, $O(n^2)$. In the average case, every element shifts about half the length of the sorted segment; still quadratic, but with a smaller constant.

The Inversion Count

Insertion sort’s cost can be measured exactly by how “disordered” the input is.

An inversion is a pair where $i < j$ but $d_i > d_j$. A sorted array has zero, a reverse-sorted array has $n(n-1)/2$.

Every shift insertion sort performs eliminates exactly one inversion; therefore the total number of shifts equals the number of inversions, and the cost is $O(n + \text{inversions})$.

def inversion_count(array: list[int]) -> int:
    return sum(1 for i in range(len(array))
                 for j in range(i + 1, len(array)) if array[i] > array[j])


def insertion_shift_count(array: list[int]) -> int:
    d, count = list(array), 0
    for i in range(1, len(d)):
        key, j = d[i], i - 1
        while j >= 0 and d[j] > key:
            d[j + 1] = d[j]
            j -= 1
            count += 1
        d[j + 1] = key
    return count


for example in ([1, 2, 3, 4, 5], [5, 2, 9, 1, 5, 6], [5, 4, 3, 2, 1]):
    print(example, inversion_count(example), insertion_shift_count(example))

# [1, 2, 3, 4, 5] 0 0
# [5, 2, 9, 1, 5, 6] 6 6
# [5, 4, 3, 2, 1] 10 10

The two columns being equal in every row is not a coincidence; it is the exact definition of what the algorithm does. The result matters in practice: on nearly sorted data, insertion sort runs close to linear. An array formed by adding a few new records to an already sorted log fits this description.

Comparison

Criterion	Bubble	Selection	Insertion
Best case	$O(n)$ (with flag)	$O(n^2)$	$O(n)$
Average / worst	$O(n^2)$	$O(n^2)$	$O(n^2)$
Move count	$O(n^2)$	$O(n)$	$O(n^2)$
Stable	Yes	No	Yes
In-place	Yes	Yes	Yes
Adaptive	Yes	No	Yes

All three are in the quadratic class; the difference between them is in constants and secondary criteria. In practice, insertion sort stands out on small arrays and nearly sorted data — which is why advanced sorting implementations switch to it for small segments.

Bubble sort has no clear advantage; its instructional value is that it is the plainest form of the adjacent-swap idea.

Summary

• The sorting problem requires two conditions: the output must be ordered, and it must be a permutation of the input.
• Algorithms are distinguished by stability, in-place operation, and adaptivity; comparisons and moves are counted separately.
• Bubble sort works by adjacent swaps; an early-exit flag brings the best case down to linear.
• Selection sort always makes quadratic comparisons but a linear number of moves; in this form it is not stable.
• Insertion sort is stable, in-place, and adaptive; its shift count equals the inversion count.
• All three are in the quadratic class; the difference is in constants and secondary criteria.

Next Step

As the scale-growth table showed, the quadratic class could not be used on data in the millions. The next lesson applies the divide-and-conquer idea, whose recurrence was solved in the complexity calculation lesson, to sorting: merge sort delivers an $O(n \log n)$ guarantee together with stability.