Selection, bubble and insertion sort

Selection sort, bubble sort and insertion sort are the three elementary sorts. Each one grows a sorted part of the array by one item per pass, using only comparisons and swaps or shifts, and each takes about n²/2 comparisons in the worst case. Selection sort finds the smallest remaining item and swaps it into place. Bubble sort walks the array and swaps neighbours that are out of order, so the largest remaining item sinks to the end. Insertion sort takes the next item and shifts the larger items of the sorted part one place right until the new item fits. They are worth knowing because they differ in what they save: selection sort makes few swaps, bubble sort and insertion sort stop early on sorted input, and insertion sort’s work is exactly the disorder of its input. This lesson traces all three on the same eight numbers with every comparison and swap counted.

Three ways to grow a sorted part

Each sort keeps an invariant, a statement about the array that is true after every pass:

• Selection sort: after pass i, the first i places hold the i smallest items in order. Each pass compares every remaining item with the smallest found so far, so the comparisons are always n(n − 1)/2, while the swaps are at most n − 1, one per pass.
• Bubble sort: after pass i, the last i places hold the i largest items in order. A pass that makes no swap proves that the array is sorted, so with that early exit sorted input costs only n − 1 comparisons.
• Insertion sort: after pass i, the first i + 1 items of the input are sorted among themselves, although later items may still land between them. Each shift moves one larger item past the item being inserted.

Bubble sort and insertion sort only ever move an item past a strictly larger neighbour, so equal items keep their order and both sorts are stable. Selection sort’s swap can carry an item a long way, past items equal to it, so it is not stable in its usual array form.

The three sorts traced on eight numbers

This program runs all three sorts on 5, 2, 8, 1, 9, 3, 7, 4 and prints the array after every pass:

"""Selection, bubble and insertion sort on the same 8 numbers, with every pass printed and the work counted."""


def selection_sort(a, show):
    a = list(a)
    comparisons = swaps = 0
    for i in range(len(a) - 1):
        smallest = i
        for j in range(i + 1, len(a)):
            comparisons += 1
            if a[j] < a[smallest]:
                smallest = j
        if smallest != i:
            a[i], a[smallest] = a[smallest], a[i]
            swaps += 1
        show(i + 1, a)
    return comparisons, swaps


def bubble_sort(a, show):
    a = list(a)
    comparisons = swaps = 0
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for j in range(end):
            comparisons += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swaps += 1
                swapped = True
        show(len(a) - end, a)
        if not swapped:  # a pass without a swap: the array is sorted
            break
    return comparisons, swaps


def insertion_sort(a, show):
    a = list(a)
    comparisons = shifts = 0
    for i in range(1, len(a)):
        item = a[i]
        j = i
        while j > 0:
            comparisons += 1
            if a[j - 1] <= item:
                break
            a[j] = a[j - 1]  # shift the larger item one place right
            shifts += 1
            j -= 1
        a[j] = item
        show(i, a)
    return comparisons, shifts


data = [5, 2, 8, 1, 9, 3, 7, 4]
print("input   ", data)
for sort, moves in [(selection_sort, "swaps"), (bubble_sort, "swaps"), (insertion_sort, "shifts")]:
    print(sort.__name__)
    comparisons, work = sort(data, lambda k, a: print(f"  pass {k}", a))
    print(f"  {comparisons} comparisons, {work} {moves}")

input    [5, 2, 8, 1, 9, 3, 7, 4]
selection_sort
  pass 1 [1, 2, 8, 5, 9, 3, 7, 4]
  pass 2 [1, 2, 8, 5, 9, 3, 7, 4]
  pass 3 [1, 2, 3, 5, 9, 8, 7, 4]
  pass 4 [1, 2, 3, 4, 9, 8, 7, 5]
  pass 5 [1, 2, 3, 4, 5, 8, 7, 9]
  pass 6 [1, 2, 3, 4, 5, 7, 8, 9]
  pass 7 [1, 2, 3, 4, 5, 7, 8, 9]
  28 comparisons, 5 swaps
bubble_sort
  pass 1 [2, 5, 1, 8, 3, 7, 4, 9]
  pass 2 [2, 1, 5, 3, 7, 4, 8, 9]
  pass 3 [1, 2, 3, 5, 4, 7, 8, 9]
  pass 4 [1, 2, 3, 4, 5, 7, 8, 9]
  pass 5 [1, 2, 3, 4, 5, 7, 8, 9]
  25 comparisons, 13 swaps
insertion_sort
  pass 1 [2, 5, 8, 1, 9, 3, 7, 4]
  pass 2 [2, 5, 8, 1, 9, 3, 7, 4]
  pass 3 [1, 2, 5, 8, 9, 3, 7, 4]
  pass 4 [1, 2, 5, 8, 9, 3, 7, 4]
  pass 5 [1, 2, 3, 5, 8, 9, 7, 4]
  pass 6 [1, 2, 3, 5, 7, 8, 9, 4]
  pass 7 [1, 2, 3, 4, 5, 7, 8, 9]
  18 comparisons, 13 shifts

Selection sort made 28 comparisons, 7 + 6 + … + 1, and only 5 swaps: passes 2 and 7 found the smallest item already in place. Bubble sort made 13 swaps and stopped after pass 5, when a pass found nothing to swap. Insertion sort needed 18 comparisons and 13 shifts. The two 13s are not a coincidence: the input has exactly 13 inversions, pairs of items that stand in the wrong order, such as 5 before 2 or 9 before 3. Every bubble-sort swap and every insertion-sort shift puts exactly one such pair right.

The three side by side:

• Selection sort: always n(n − 1)/2 comparisons, at most n − 1 swaps; not stable and not adaptive.
• Bubble sort with an early exit: n − 1 comparisons on sorted input and n(n − 1)/2 at worst, one swap per inversion; stable and adaptive.
• Insertion sort: n − 1 comparisons on sorted input and n(n − 1)/2 at worst, one shift per inversion; stable and adaptive.

Selection sort is the one to pick when every write is expensive, bubble sort is mostly a teaching tool, and insertion sort is the practical choice for short or nearly sorted input.

That is why insertion sort is fast on nearly sorted data: an array whose items are each at most a few places from their final positions has few inversions, so it costs about n comparisons plus one shift per inversion. Shuffled data has about n²/4 inversions on average, so all three sorts are quadratic there.

Exercise and self-check

Write the insertion sort that counts its shifts. The sample tests check, on 200 random lists, that the count equals the number of inversions.

def insertion_sort(a):
    """Sorts a in place with insertion sort and returns the number of shifts it made."""
    shifts = 0
    # Write the insertion sort here.
    return shifts

import random

from shifts import insertion_sort


class Card:
    """A card compared by its number only; the letter shows where it started."""

    def __init__(self, number, letter):
        self.number, self.letter = number, letter

    def __gt__(self, other):
        return self.number > other.number

    def __lt__(self, other):
        return self.number < other.number


def test_small_lists():
    """sorts small lists in place and returns their shift counts"""
    for values, shifts in [([5, 2, 8, 1, 9, 3, 7, 4], 13), ([], 0), ([42], 0), ([1, 2, 3], 0), ([3, 2, 1], 3)]:
        a = list(values)
        assert insertion_sort(a) == shifts, values
        assert a == sorted(values), values


def test_equal_items_keep_their_order():
    """equal items keep their input order"""
    cards = [Card(3, "a"), Card(1, "b"), Card(3, "c"), Card(2, "d"), Card(1, "e")]
    insertion_sort(cards)
    assert [c.letter for c in cards] == ["b", "e", "d", "a", "c"]


def test_shifts_equal_inversions():
    """on 200 random lists, the shift count equals the number of out-of-order pairs"""
    rng = random.Random(4)
    for _ in range(200):
        values = [rng.randint(0, 9) for _ in range(rng.randint(0, 30))]
        expected = sum(1 for i in range(len(values)) for j in range(i + 1, len(values)) if values[i] > values[j])
        a = list(values)
        assert insertion_sort(a) == expected, values
        assert a == sorted(values), values

/** Sorts a in place with insertion sort and returns the number of shifts it made. */
export function insertionSort(a) {
  let shifts = 0;
  // Write the insertion sort here.
  return shifts;
}

import { test, assert } from 'mysmartcopilot:test';
import { insertionSort } from './shifts.mjs';

/** A card compared by its number only (through valueOf); the letter shows where it started. */
class Card {
  constructor(number, letter) {
    this.number = number;
    this.letter = letter;
  }
  valueOf() {
    return this.number;
  }
}

const sortedCopy = (values) => values.slice().sort((x, y) => x - y);

test('sorts small lists in place and returns their shift counts', () => {
  for (const [values, shifts] of [[[5, 2, 8, 1, 9, 3, 7, 4], 13], [[], 0], [[42], 0], [[1, 2, 3], 0], [[3, 2, 1], 3]]) {
    const a = values.slice();
    assert.equal(insertionSort(a), shifts, JSON.stringify(values));
    assert.equal(a.join(','), sortedCopy(values).join(','), JSON.stringify(values));
  }
});

test('equal items keep their input order', () => {
  const cards = [new Card(3, 'a'), new Card(1, 'b'), new Card(3, 'c'), new Card(2, 'd'), new Card(1, 'e')];
  insertionSort(cards);
  assert.equal(cards.map((c) => c.letter).join(''), 'bedac');
});

test('on 200 random lists, the shift count equals the number of out-of-order pairs', () => {
  let seed = 4;
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  for (let k = 0; k < 200; k++) {
    const values = Array.from({ length: Math.floor(random() * 31) }, () => Math.floor(random() * 10));
    let expected = 0;
    for (let i = 0; i < values.length; i++) for (let j = i + 1; j < values.length; j++) if (values[i] > values[j]) expected++;
    const a = values.slice();
    assert.equal(insertionSort(a), expected, JSON.stringify(values));
    assert.equal(a.join(','), sortedCopy(values).join(','), JSON.stringify(values));
  }
});

Why each sort is correct, and its exact counts Pro: opens with a Pro, Premium or Ultimate pass

Stability and nearly sorted data, reproduced and measured Pro: opens with a Pro, Premium or Ultimate pass

Insertion sort in five languages, with variants and practice Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Selection sort always makes n(n − 1)/2 comparisons and at most n − 1 swaps, and it is not stable.
• Bubble sort with an early exit and insertion sort are stable and adaptive: n − 1 comparisons on sorted input.
• Every bubble-sort swap and every insertion-sort shift fixes exactly one inversion, so both do one move per inversion.
• Insertion sort costs about n plus the number of inversions, which is why it suits nearly sorted data.