Searching, Sorting and Big O

Ava has ten thousand customers, and wants to find one by name. Checking them one by one works, but takes a while. If the list is sorted, she can open it in the middle, like a phone book, and halve the work at every step. The choice of algorithm decides whether a program takes a blink, or an hour.

• Ten thousand customers
• Check one by one, or halve each time?
• Algorithms decide the speed

Big O: how work grows

Computer scientists describe speed with Big O notation. It tells how the work grows, as the data grows. Constant time, written O of one, does not grow. Logarithmic time grows very slowly. Linear time doubles when the data doubles. And quadratic time explodes, ten times the data, a hundred times the work. Aim for the slow growing ones.

Linear search

The simplest search checks each item, from the start. If the list has n items, we may check all n. That is linear time. Here we count the checks it takes to find a customer near the end of a list. It works on any list, sorted or not, but it is slow for big data.

def linear(items, target):
    checks = 0
    for i, x in enumerate(items):
        checks += 1
        if x == target:
            return i, checks
    return -1, checks

names = [f"cust{n:04d}" for n in range(1000)]
print(linear(names, "cust0900"))

(900, 901)

Binary search

If the list is sorted, we can do better. Look at the middle item. If the target is smaller, discard the upper half, otherwise discard the lower half. Repeat. Every step halves the problem, so a thousand items need about ten checks, and a million items need only twenty. The bisect module in the standard library does exactly this.

def binary(items, target):
    lo, hi, checks = 0, len(items) - 1, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        checks += 1
        if items[mid] == target:
            return mid, checks
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, checks

names = [f"cust{n:04d}" for n in range(1000)]
print(binary(names, "cust0900"))
import bisect
print(bisect.bisect_left(names, "cust0900"))

(900, 10)
900

Sorting: by hand and built in

Sorting is a classic problem. Here is a simple bubble sort, which swaps neighbours until all items are in order. It takes quadratic time, and is fine for learning. Python's built in sort, called Timsort, takes n log n, is stable, and is much faster. In real code, always use sorted, or the sort method.

def bubble(a):
    a = a[:]
    for i in range(len(a)):
        for j in range(len(a) - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

data = [9, 3, 7, 1, 8]
print(bubble(data))
print(sorted(data))
print(sorted(["fern", "Ivy", "rose"], key=str.lower))

[1, 3, 7, 8, 9]
[1, 3, 7, 8, 9]
['fern', 'Ivy', 'rose']

Measuring speed

Never guess performance, measure it. The timeit module runs a snippet many times, and reports the time. Here we compare looking up an item in a list, with looking it up in a set. The set uses hashing, so it takes constant time, and wins by a huge margin as the data grows.

import timeit

items = list(range(10_000))
as_set = set(items)
t_list = timeit.timeit("9_999 in items", globals=globals(), number=2000)
t_set = timeit.timeit("9_999 in as_set", globals=globals(), number=2000)
print("set is much faster:", t_list / t_set > 20)

set is much faster: True

Count the checks

Your turn. Write a function that finds the position of a number in a sorted list, using the bisect module, and returns minus one, when the number is not there. Ready? Here is one solution. Bisect left finds the position, and we check that the item is really there.

import bisect

def find(nums, x):
    i = bisect.bisect_left(nums, x)
    return i if i < len(nums) and nums[i] == x else -1

print(find([1, 3, 5, 7], 5))
print(find([1, 3, 5, 7], 4))

2
-1

Summary