Quicksort picks a pivot, partitions (smaller left, larger right), then recurses. Average Θ(n log n). Worst Θ(n²) if every pivot is the extreme.

Goal

Partition a price list, then quicksort it. Count comparisons.

Partition

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

xs = [31, 10.5, 22.0, 10.5, 7]
idx, steps = partition(xs, 0, len(xs) - 1)
print("pivot index", idx, "steps", steps, "xs", xs)

Recurse

def quicksort(xs, lo=0, hi=None, steps=0):
    if hi is None:
        hi = len(xs) - 1
        xs = list(xs)
    if lo >= hi:
        return xs, steps
    pivot = xs[hi]
    i = lo
    for j in range(lo, hi):
        steps += 1
        if xs[j] <= pivot:
            xs[i], xs[j] = xs[j], xs[i]
            i += 1
    xs[i], xs[hi] = xs[hi], xs[i]
    xs, steps = quicksort(xs, lo, i - 1, steps)
    xs, steps = quicksort(xs, i + 1, hi, steps)
    return xs, steps

print(quicksort([31, 10.5, 22.0, 10.5, 7]))
print(quicksort([1, 2, 3, 4, 5]))

Already-sorted input with last-element pivot is the ugly case: one side empty each time.

Pitfall

This is not list.sort (Timsort). Production: sorted(xs). This chapter exists so average vs worst is a table you can print, not a slogan.