Quicksort in Python
Partitions around a pivot and recurses on both sides; Theta(n log n) expected and Theta(n^2) worst case.
- File
quicksort.py, 42 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/quicksort/. The authors are listed in prov/5TYMK3.jsonl.
import sys
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
# The recursion is n - 1 calls deep on a sorted input (the worst case of the page).
# Python stops at 1000 calls by default, so this module raises the limit.
sys.setrecursionlimit(max(sys.getrecursionlimit(), 20000))
def quicksort(a: list[T], lo: int = 0, hi: int | None = None) -> None:
"""Sort a[lo:hi] in place, in non-decreasing order. The pivot is the last item."""
if hi is None:
hi = len(a)
if hi - lo <= 1: # @line L1
return
p = partition(a, lo, hi) # @line L2
quicksort(a, lo, p) # @line L3
quicksort(a, p + 1, hi) # @line L4
def partition(a: list[T], lo: int, hi: int) -> int:
"""Lomuto partition of a[lo:hi] around x = a[hi - 1]. Return the final index p of x.
After the call, a[lo:p] holds the items <= x, a[p] == x, and a[p + 1:hi] holds the items > x.
"""
x = a[hi - 1] # @line L5
i = lo # @line L6
for j in range(lo, hi - 1): # @line L7
if not x < a[j]: # @line L8: a[j] <= x, with only <
a[i], a[j] = a[j], a[i] # @line L9
i += 1 # @line L10
a[i], a[hi - 1] = a[hi - 1], a[i] # @line L11
return i # @line L12
test_quicksort.py 69 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/quicksort/. The authors are listed in prov/5TYMK3.jsonl.
import itertools
import random
from quicksort import partition, quicksort
def test_example() -> None:
a = [6, 3, 9, 1, 7, 2, 8, 5]
quicksort(a)
assert a == [1, 2, 3, 5, 6, 7, 8, 9]
def test_first_partition() -> None:
a = [6, 3, 9, 1, 7, 2, 8, 5]
p = partition(a, 0, len(a))
assert p == 3
assert a == [3, 1, 2, 5, 7, 9, 8, 6]
def test_partition_postcondition() -> None:
rng = random.Random(7)
for _ in range(300):
a = [rng.randint(0, 9) for _ in range(rng.randint(1, 30))]
old = sorted(a)
x = a[-1]
p = partition(a, 0, len(a))
assert a[p] == x
assert all(v <= x for v in a[:p])
assert all(v > x for v in a[p + 1 :])
assert sorted(a) == old
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 1, 1], [3, 2, 1], [1, 2, 3]):
b = list(a)
quicksort(b)
assert b == sorted(a)
def test_subrange() -> None:
a = [9, 5, 4, 3, 2, 0]
quicksort(a, 1, 5)
assert a == [9, 2, 3, 4, 5, 0]
def test_all_permutations() -> None:
for n in range(7):
for p in itertools.permutations(range(n)):
b = list(p)
quicksort(b)
assert b == list(range(n))
def test_sorted_worst_case() -> None:
a = list(range(3000))
quicksort(a)
assert a == list(range(3000))
def test_random_against_sorted() -> None:
rng = random.Random(2150)
for _ in range(500):
a = [rng.randint(-50, 50) for _ in range(rng.randint(0, 60))]
b = list(a)
quicksort(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build