---
title: 'Bubble, Selection, and Insertion Sort'
source: 'https://academia.sh/en/courses/algorithms/basic-sorts'
course: Algorithms
language: en
updated: '2026-08-17T18:07:39+00:00'
license: 'CC BY-SA 4.0'
---

# Bubble, Selection, and Insertion Sort

The definition of the sorting problem, the criteria of stability and in-place operation, the comparison and move costs of three quadratic algorithms, and the inversion count.

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.

```python
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.

```python
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.

```python
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.

```python
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})$.

```python
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.