Selection, insertion and bubble sort

Sorting puts values in order, smallest first. This lesson starts with three simple methods. They are slow on large lists, but they show the ideas every faster sort builds on, and one of them is still the best choice for small or nearly sorted lists.

Why sorting matters

A sorted list answers many questions quickly: binary search (BSRC), the smallest and largest values, repeats (they end up side by side), and pairs that add up to a target (ARRS-2). Many algorithms start with “sort the input”. In Python you will usually call sorted(), but knowing how sorts work tells you what that call costs and when you can do better.

Three simple sorts

Step through each one on the same list. Watch the counters.

Insertion sort

Pass i takes the value key = a[i] and moves it left into the sorted part. This is the core of one pass, with j starting at i − 1:

while j >= 0 and a[j] > key:
    a[j + 1] = a[j]      # move the bigger value right
    j -= 1
a[j + 1] = key

The passes run for i = 1, 2, …, n − 1. Writing the whole sort is SORT-P1.

Each pass inserts a[i] into the sorted part, so the invariant moves on by one. When i reaches n, the whole list is sorted.

The cost depends on the input. Call a pair of positions i < j with a[i] > a[j] an inversion: a pair in the wrong order. Each move in the inner loop fixes exactly one inversion. So insertion sort takes O(n + I) time, where I is the number of inversions: time in proportion to n plus the number of inversions. A sorted list has none, so it takes O(n). A reversed list has n(n − 1) / 2 (n times n − 1, halved), so it takes O(n²).

Selection sort and bubble sort

Selection sort finds the smallest value left and swaps it to the front of the unsorted part. It always makes n(n − 1) / 2 comparisons, even on a sorted list. Its one strength is that it makes at most n − 1 swaps, which matters when writing a value is very costly.

Bubble sort swaps neighbours that are out of order, pass after pass, and can stop early after a pass with no swaps. Each swap also fixes exactly one inversion, so it does as many swaps as insertion sort does moves, plus more comparisons.

Which to use

“Stable” means equal values keep their original order; lesson 7 explains why that matters. All three sort in place, with O(1) extra space.

Now try SORT-P1, Nearly in order.