Algorithms in Motion

Linear search examines each element until a match is found. O(n) worst and average, O(1) best.

def linear_search(a, target):
    for i, v in enumerate(a):
        if v == target:
            return i
    return -1

# works on ANY order, zero preparation
# O(n) — and O(n) to prove absence

Binary search repeatedly compares the middle element of a sorted range and discards the half that cannot contain the target, giving O(log n) time and O(1) space. It requires sorted, randomly-accessible data — the precondition is the whole trick..

def binary_search(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == t:
            return mid
        if a[mid] < t:
            lo = mid + 1      # left half impossible
        else:
            hi = mid - 1      # right half impossible
    return -1

import bisect            # the stdlib version
bisect.bisect_left(a, t)

Bubble sort repeatedly traverses the array, swapping adjacent out-of-order pairs. Each pass places the largest unsorted element at its final index.

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            return a          # early exit -> O(n)
    return a

Selection sort finds the minimum of the unsorted region and swaps it into position i. Comparisons are always n(n−1)/2 — O(n²) regardless of input — but writes are only O(n), which matters when writes are expensive.

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        lo = i
        for j in range(i + 1, n):
            if a[j] < a[lo]:
                lo = j
        a[i], a[lo] = a[lo], a[i]   # one swap per round
    return a

Insertion sort grows a sorted prefix, shifting elements right to place each new key. O(n²) worst case but O(n) on nearly-sorted input and very low constant factors, which is why real sorts fall back to it for small subarrays.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]      # slide right
            j -= 1
        a[j + 1] = key
    return a
# nearly-sorted input -> nearly O(n)

A recursive function calls itself on a smaller input and terminates at a base case; each call consumes a stack frame, so depth costs O(depth) space. Missing or unreachable base cases cause stack overflow; tail calls or an explicit stack convert recursion to iteration..

def count(doll):
    if doll.inner is None:
        return 1                 # base case
    return 1 + count(doll.inner)

import sys
sys.getrecursionlimit()   # 1000 by default
# every pending call costs a stack frame

Merge sort divides the array in half recursively and merges sorted halves in linear time. Depth log n × O(n) merge work gives O(n log n) in all cases, at the cost of O(n) auxiliary space.

def merge_sort(a):
    if len(a) < 2:
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]),
                 merge_sort(a[mid:]))

def merge(x, y):
    out = []
    while x and y:
        out.append(x.pop(0) if x[0] <= y[0] else y.pop(0))
    return out + x + y

Quicksort partitions around a pivot so that the pivot reaches its final index, then recurses on each side. Average O(n log n) with excellent cache behaviour and O(log n) stack space; worst case O(n²) on adversarial pivots, mitigated by randomised or median-of-three selection..

def quick_sort(a, lo=0, hi=None):
    hi = len(a) - 1 if hi is None else hi
    if lo >= hi:
        return a
    p = partition(a, lo, hi)
    quick_sort(a, lo, p - 1)
    quick_sort(a, p + 1, hi)
    return a

def partition(a, lo, hi):
    pivot, i = a[hi], lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

BFS explores vertices in non-decreasing order of distance from the source using a queue, visiting each vertex and edge once for O(V+E). On unweighted graphs it yields shortest paths; the queue may hold O(V) vertices..

from collections import deque

def bfs(adj, start):
    seen = {start}
    q = deque([start])
    order = []
    while q:
        v = q.popleft()          # FIFO
        order.append(v)
        for w in adj[v]:
            if w not in seen:
                seen.add(w)
                q.append(w)
    return order

DFS follows each branch to exhaustion before backtracking, using an explicit stack or recursion, in O(V+E). It does not give shortest paths, but it is the basis of cycle detection, topological sorting and connected-component labelling..

def dfs(adj, start):
    seen, stack, order = set(), [start], []
    while stack:
        v = stack.pop()          # LIFO
        if v in seen:
            continue
        seen.add(v)
        order.append(v)
        stack.extend(adj[v])
    return order