Algorithms – searching and sorting

What you'll learn

Understand what an algorithm is
Compare linear and binary search
Program a sorting algorithm yourself

What is an algorithm?

An algorithm is an exact step-by-step set of instructions that solves a problem – like a recipe, just for computers. There are often several algorithms for the same problem, and some are much faster than others.

Searching: page by page …

The simplest search looks at every element in turn. It’s called linear search:

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1


print(linear_search([7, 3, 9, 4], 9))

With a million entries, in the worst case it needs a million comparisons.

… or like in a dictionary

If the list is sorted, it’s much faster: look in the middle. If the value you want is bigger, it can only be in the right half – the left half drops out completely. That’s binary search. Every step halves the list:

count = 1_000_000
steps = 0
while count > 1:
    count //= 2
    steps += 1
print("A million entries – at most", steps, "steps")

Instead of a million comparisons, about 20 are enough!

Sorting with bubble sort

Python has sorted(), but how does sorting actually work? The simplest algorithm is called bubble sort: always compare two neighbours and swap them if they’re the wrong way round. After every round, the biggest number has “bubbled up” to the end:

numbers = [5, 1, 4, 2]
for rnd in range(len(numbers)):
    for i in range(len(numbers) - 1):
        if numbers[i] > numbers[i + 1]:
            numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]   # swap
    print("After round", rnd + 1, ":", numbers)

The swapping trick – a, b = b, a – works in a single line thanks to tuples.

Good to know: bubble sort is nice and simple, but slow. Python’s own sorted() uses a much cleverer algorithm called Timsort – named after Tim Peters, who invented it for Python in 2002.

Quick check

How many steps does binary search need at most with 16 entries? What does this program print?

n = 16
steps = 0
while n > 1:
    n //= 2
    steps += 1
print(steps)

Your task

Your turn

Program two classics yourself – without sorted(), .sort() or .index(). binary_search(lst, target) searches a sorted list and returns the position of target (or -1 if it isn't there). bubble_sort(lst) returns a new list sorted in ascending order and leaves the old one unchanged.

def binary_search(lst, target):
    pass


def bubble_sort(lst):
    pass


print(binary_search([2, 5, 8, 12, 16, 23], 12))
print(bubble_sort([5, 1, 4, 2, 8]))

Something to think about
Keep track of left and right. Look in the middle – if the value there is too small, carry on searching to the right, otherwise to the left.
Which command helps?
The loop runs while left <= right. After that, return -1.
First copy the list with list(lst). Then always compare two neighbours and swap them if they're the wrong way round.

Gap code – fill in the ___

                        def binary_search(lst, target):
    left, right = ___
    while ___:
        middle = ___
        if ___:
            return ___
        if ___:
            left = ___
        else:
            right = ___
    return ___


def bubble_sort(lst):
    numbers = ___
    for rnd in ___:
        for i in ___:
            if ___:
                ___
    return ___


print(binary_search([2, 5, 8, 12, 16, 23], 12))
print(bubble_sort([5, 1, 4, 2, 8]))

Solve it without hints to earn a ⭐ on your progress page.

Show solution

Try it yourself first – mistakes teach you the most. Here is one possible solution:

def binary_search(lst, target):
    left, right = 0, len(lst) - 1
    while left <= right:
        middle = (left + right) // 2
        if lst[middle] == target:
            return middle
        if lst[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return -1


def bubble_sort(lst):
    numbers = list(lst)
    for rnd in range(len(numbers)):
        for i in range(len(numbers) - 1 - rnd):
            if numbers[i] > numbers[i + 1]:
                numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
    return numbers


print(binary_search([2, 5, 8, 12, 16, 23], 12))
print(bubble_sort([5, 1, 4, 2, 8]))