Searching and sorting

Computers search all day: your contacts, a shop's stock, a game's leaderboard, Google's index. Most of that data is sorted first, because sorted data is much faster to search.

1. An algorithm is a recipe. Exact, ordered steps that always finish. Searching and sorting are the classic examples.

2. We measure speed by counting. Not seconds: computers differ. We count comparisons: each time the algorithm asks "is this the one?" or "is this bigger than that?".

3. We care about big lists. On 8 items every method is instant. On 8 million, a bad choice can take days instead of a blink.

Linear search starts at the first item and checks each one in turn. It stops when it finds the item, or when it runs out of items.

1. Start at the first item (index 0).

2. Is it the target? Yes → stop and report where it is.

3. No → move to the next item and repeat.

4. If you pass the last item without finding it, report "not found".

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i      # found: give back its index
    return -1             # checked them all: not there

scores = [12, 45, 33, 7, 50, 28]
print(linear_search(scores, 7))

Binary search needs a sorted list. Like a dictionary: open it in the middle, decide which half your word is in, throw the other half away. Repeat.

1. Look at the middle item. (Middle index = (low + high) ÷ 2, rounded down.)

2. Is it the target? Stop, found.

3. Is the target bigger? Throw away the middle and everything left of it. Smaller? Throw away the middle and everything right of it.

4. Repeat with what's left. If nothing is left, the target is not in the list.

How many checks, at most?

Each check halves what's left. So the question is: how many times can you halve n before you get down to 1? That number has a name: log₂ n ("log base 2 of n").

By hand, for n = 1,000. Press Next line.

1. Halve, rounding down each time: 1,000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1.

2. Count the arrows: 9 halvings. So ⌊log₂ 1,000⌋ = 9.

3. Check it the other way, by doubling: 2⁹ = 512 is not more than 1,000, but 2¹⁰ = 1,024 is. So 9 is the biggest power that fits.

4. The last item left still needs one more check: 9 + 1 = 10 checks.

5. Compare: linear search could need 1,000 checks on the same list. Binary search needs at most 10.

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1     # throw away the left half
        else:
            high = mid - 1    # throw away the right half
    return -1                 # nothing left: not there

Plot "most checks needed" against "items in the list". Linear search climbs in a straight line. Binary search barely leaves the floor.

Bubble sort walks along the list comparing neighbours. If a pair is in the wrong order, it swaps them. One trip along the list is called a pass.

1. Compare items 0 and 1. Wrong order? Swap them.

2. Move one place right: compare items 1 and 2. Then 2 and 3, and so on to the end. That's one pass.

3. After pass 1, the biggest item is at the end, in its final place. After pass 2, the second biggest is too. So each pass can stop one place earlier.

4. Early stop: if a whole pass makes no swaps, the list is sorted. Stop.

How many comparisons, at most?

The worst case is a list in reverse order: every pass swaps every pair. With n items, pass 1 compares n − 1 pairs, pass 2 compares n − 2, … down to 1.

By hand, for n = 5. Press Next line.

1. Passes compare 4, then 3, then 2, then 1 pairs. Total: 4 + 3 + 2 + 1.

2. Pair them up from the outside in: (4 + 1) and (3 + 2).

3. Every pair adds to 5, which is n. There are 4 numbers, so (n − 1) ÷ 2 = 2 pairs.

4. 2 pairs × 5 = 10. That's n × (n − 1) ÷ 2 = 5 × 4 ÷ 2 = 10.

5. Same trick for n = 100: 100 × 99 ÷ 2 = 4,950 comparisons. For n = 1,000: 499,500. Ten times the items, about a hundred times the work.

def bubble_sort(items):
    n = len(items)
    swapped = True
    while swapped:
        swapped = False
        for i in range(n - 1):
            if items[i] > items[i + 1]:
                # swap the neighbours
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        n = n - 1   # the last one is now in place
    return items

Insertion sort keeps a sorted part on the left. It picks up the next item from the unsorted part and slides it left into its correct place.

1. The first item on its own counts as sorted.

2. Pick up the first unsorted item. This leaves a gap.

3. Compare it with the item to the left of the gap. Bigger than yours? Shift it right into the gap. Repeat.

4. Smaller (or the front of the list)? Drop your item into the gap. The sorted part has grown by one.

def insertion_sort(items):
    for i in range(1, len(items)):
        key = items[i]        # pick up the next card
        j = i - 1
        while j >= 0 and items[j] > key:
            items[j + 1] = items[j]   # shift right
            j = j - 1
        items[j + 1] = key    # drop it into the gap
    return items

Merge sort splits the list in half again and again until every piece has 1 item. A list of 1 is already sorted. Then it merges pieces back together, in order, two at a time.

1. Split: [6, 3, 8, 1] [5, 2, 7, 4]

2. Split: [6, 3] [8, 1] [5, 2] [7, 4]

3. Split into singles. Each single is sorted.

4. Merge: [3, 6] [1, 8] [2, 5] [4, 7]

5. Merge: [1, 3, 6, 8] [2, 4, 5, 7]

6. Merge: [1, 2, 3, 4, 5, 6, 7, 8]

def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # compare the fronts
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1
    return result + left[i:] + right[j:]   # copy what's left

def merge_sort(items):
    if len(items) <= 1:
        return items                       # 1 item: sorted
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))

There's rarely one best algorithm. There's only the best one for this data: how big it is, how messy it is, and how much memory you have.

Computer scientists describe speed by asking one question: if the list gets bigger, how fast does the work grow? The answer is written with a capital O, for "order of". (This is A-level, but the idea is simple.)

1. Say a computer does 1 million comparisons a second.

2. Sorting 1 million items with an n² sort: 10¹² ÷ 10⁶ = 1,000,000 seconds. That's about 11.6 days.

3. With an n log n sort: 20,000,000 ÷ 1,000,000 = 20 seconds.

4. Same computer. Same data. The algorithm made the difference between a coffee break and a fortnight.

A sorting network is a fixed set of "compare and swap" stations. Numbers travel along lanes. At each station two lanes meet: the smaller number goes up, the bigger goes down. At the end they're sorted, every time.

1. 12 stations in 5 stages. Stations in the same stage never share a lane, so they can all happen at the same time. That's parallel processing, like the many cores in a graphics card.

2. It never changes its plan. The same 12 comparisons happen whatever the numbers are. Bubble sort's comparisons depend on the data; a network's don't.

3. The weighing version. Give a group 8 identical pots with different amounts of sand, and one balance scale. The only allowed question is "which of these two is heavier?" That is exactly one comparison. Sort the pots, and count how many weighings it took.

The mistakes nearly everyone makes the first time. Read the left side, then the right.

Quick questions first. Then endless practice: a wrong answer shows you the working, step by step.