Bubble, Selection & Insertion Sort

Sorting means arranging items in order, such as marks from lowest to highest or names from A to Z. Sorted data is easier to search (binary search), to group (duplicates sit next to each other) and to read. Sorting is also the classic place to practise analysing algorithms.

In this lesson you will write the three simple sorting algorithms that every course and exam starts with: bubble sort, selection sort and insertion sort. They are all O(n²) in the worst case, but they behave differently, and insertion sort is still used inside Python's own sort today.

Words you need

• Comparison: checking which of two items is smaller. Sorting algorithms are usually measured by how many comparisons they make.
• In-place: the algorithm rearranges the list itself, using only O(1) extra memory.
• Stable: items that compare equal keep their original order. If two students both score 78, a stable sort keeps them in the order they were listed.

Bubble sort

Bubble sort walks through the list comparing neighbours and swapping any pair that is in the wrong order. After the first pass, the largest item has "bubbled" to the end. After the second pass, the second largest is in place, and so on. If a whole pass makes no swaps, the list is sorted and you can stop early.

def bubble_sort(items):
    items = items[:]                       # work on a copy
    n = len(items)
    for done in range(n - 1):
        swapped = False
        for i in range(n - 1 - done):      # the last 'done' items are in place
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        print(f"after pass {done + 1}: {items}")
        if not swapped:
            break                          # no swaps: already sorted
    return items

bubble_sort([64, 25, 12, 22, 11])

after pass 1: [25, 12, 22, 11, 64]
after pass 2: [12, 22, 11, 25, 64]
after pass 3: [12, 11, 22, 25, 64]
after pass 4: [11, 12, 22, 25, 64]

Bubble sort is in-place and stable (it only swaps neighbours that are strictly out of order). It makes about n²/2 comparisons on a random list, and with the early exit it needs only one pass, O(n), on a list that is already sorted.

Selection sort

Selection sort divides the list into a sorted part on the left and an unsorted part on the right. Each round, it selects the smallest item from the unsorted part and swaps it to the end of the sorted part.

def selection_sort(items):
    items = items[:]
    n = len(items)
    for start in range(n - 1):
        smallest = start
        for i in range(start + 1, n):
            if items[i] < items[smallest]:
                smallest = i
        items[start], items[smallest] = items[smallest], items[start]
        print(f"round {start + 1}: {items}")
    return items

selection_sort([64, 25, 12, 22, 11])

round 1: [11, 25, 12, 22, 64]
round 2: [11, 12, 25, 22, 64]
round 3: [11, 12, 22, 25, 64]
round 4: [11, 12, 22, 25, 64]

Selection sort always makes exactly n(n - 1)/2 comparisons, even on sorted data, so its best case is still O(n²). Its one advantage is that it makes at most n - 1 swaps, which matters only when writing to memory is very expensive. It is not stable: the long-distance swap can jump an item over an equal one.

Insertion sort

Insertion sort works the way most people sort playing cards in their hand. Take the next card and slide it left past every larger card until it sits in the right place. The left part of the list is always sorted.

def insertion_sort(items):
    items = items[:]
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]        # shift the bigger item right
            j -= 1
        items[j + 1] = current             # drop the card into the gap
        print(f"insert {current:>2}: {items}")
    return items

insertion_sort([64, 25, 12, 22, 11])

insert 25: [25, 64, 12, 22, 11]
insert 12: [12, 25, 64, 22, 11]
insert 22: [12, 22, 25, 64, 11]
insert 11: [11, 12, 22, 25, 64]

Insertion sort is in-place and stable. Its great strength is nearly sorted data: each new item only moves a short distance, so the running time is close to O(n). That is why Python's built-in sort uses insertion sort for short pieces of the list (see Counting Sort & Timsort).

A counting experiment

Let us count comparisons for all three algorithms on 200 items arranged three ways: random, already sorted and reversed. random.seed(7) makes the "random" list the same every time you run it.

import random

def bubble(a):
    a, c = a[:], 0
    for done in range(len(a) - 1):
        swapped = False
        for i in range(len(a) - 1 - done):
            c += 1
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
    return c

def selection(a):
    a, c = a[:], 0
    for s in range(len(a) - 1):
        m = s
        for i in range(s + 1, len(a)):
            c += 1
            if a[i] < a[m]:
                m = i
        a[s], a[m] = a[m], a[s]
    return c

def insertion(a):
    a, c = a[:], 0
    for i in range(1, len(a)):
        cur, j = a[i], i - 1
        while j >= 0:
            c += 1
            if a[j] <= cur:
                break
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = cur
    return c

random.seed(7)
n = 200
cases = {"random": random.sample(range(1000), n),
         "sorted": list(range(n)),
         "reversed": list(range(n, 0, -1))}
print(f"{'input':>9} {'bubble':>7} {'selection':>10} {'insertion':>10}")
for name, data in cases.items():
    print(f"{name:>9} {bubble(data):>7} {selection(data):>10} {insertion(data):>10}")

   input  bubble  selection  insertion
  random   19879      19900       9697
  sorted     199      19900        199
reversed   19900      19900      19900

The table matches the theory. On reversed data, all three do n(n - 1)/2 = 19,900 comparisons, their worst case. On sorted data, bubble sort (with early exit) and insertion sort finish in one pass of 199 comparisons, while selection sort still does all 19,900. On random data, insertion sort does about half the work of the other two.

Why stability matters

Stability lets you sort by several keys in steps. Suppose a teacher in Rohtak already has students in alphabetical order and now sorts them by marks. With a stable sort, students with equal marks stay in alphabetical order, so you get "by marks, then by name" for free.

students = [("Aarav", 78), ("Isha", 91), ("Kabir", 78), ("Meera", 65), ("Rohan", 85)]

def insertion_by_marks(rows):                # stable
    rows = rows[:]
    for i in range(1, len(rows)):
        cur, j = rows[i], i - 1
        while j >= 0 and rows[j][1] > cur[1]:
            rows[j + 1] = rows[j]
            j -= 1
        rows[j + 1] = cur
    return rows

def selection_by_marks(rows):                # not stable
    rows = rows[:]
    for s in range(len(rows) - 1):
        m = min(range(s, len(rows)), key=lambda i: rows[i][1])
        rows[s], rows[m] = rows[m], rows[s]
    return rows

print([name for name, _ in insertion_by_marks(students)])
print([name for name, _ in selection_by_marks(students)])

['Meera', 'Aarav', 'Kabir', 'Rohan', 'Isha']
['Meera', 'Kabir', 'Aarav', 'Rohan', 'Isha']

Aarav and Kabir both scored 78. Insertion sort keeps Aarav before Kabir, as in the input. Selection sort puts Kabir before Aarav: in round 1 it swapped Aarav (at the front) with Meera (the lowest mark), and that long jump carried Aarav past Kabir. Bugs like this are easy to miss, because many inputs happen to come out right. Python's own sorted() is guaranteed to be stable.

Common mistakes

• Off-by-one in the inner loop. range(n - 1 - done) stops before comparing with the items already in place; range(n) would read past the end.
• Forgetting the early exit in bubble sort, which loses the O(n) best case.
• Using >= instead of > when shifting or swapping, which makes a stable sort unstable.
• Using an O(n²) sort for large data. For more than a few thousand items, use sorted() or an O(n log n) algorithm.

Key points

• Bubble sort swaps neighbours; selection sort selects the minimum; insertion sort inserts each item into a sorted left part.
• All three are O(n²) in the worst case and use O(1) extra space.
• Bubble (with early exit) and insertion sort are O(n) on already sorted data; selection sort never is.
• Insertion sort is excellent for small or nearly sorted lists, which is why real sorts use it for short runs.
• A stable sort keeps equal items in their original order; bubble and insertion are stable, selection is not.

def insertion_sort_desc(prices):
    prices = prices[:]
    shifts = 0
    for i in range(1, len(prices)):
        current, j = prices[i], i - 1
        while j >= 0 and prices[j] < current:    # '<' gives descending order
            prices[j + 1] = prices[j]
            shifts += 1
            j -= 1
        prices[j + 1] = current
    return prices, shifts

print(insertion_sort_desc([15999, 22999, 9999, 31999, 12499, 18999]))

([31999, 22999, 18999, 15999, 12499, 9999], 8)