Hoare partition scheme in Python
Partition scheme scanning from both ends that swaps out-of-place pairs; fewer swaps and handles duplicates well.
- File
hoare_partition.py, 48 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/hoare-partition/. The authors are listed in prov/HR9MYC.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def hoare_partition(a: list[T], lo: int, hi: int) -> int:
"""Partition a[lo..hi] (both ends included) around the pivot a[lo].
Precondition: lo < hi. Returns j with lo <= j < hi such that each item of
a[lo..j] is <= each item of a[j+1..hi]. The pivot is not always at j.
Cost: at most hi - lo + 3 comparisons and (hi - lo + 1) // 2 exchanges.
"""
x = a[lo] # @line L1
i, j = lo - 1, hi + 1 # @line L2
while True: # @line L3
j -= 1 # @line L4
while x < a[j]: # repeat until a[j] <= x
j -= 1
i += 1 # @line L5
while a[i] < x: # repeat until a[i] >= x
i += 1
if i < j: # @line L6
a[i], a[j] = a[j], a[i]
else:
return j # @line L7
def quicksort(a: list[T]) -> None:
"""Sort a in place with quicksort over hoare_partition, recursing on the smaller side."""
stack = [(0, len(a) - 1)]
while stack:
lo, hi = stack.pop()
while lo < hi:
j = hoare_partition(a, lo, hi)
if j - lo < hi - j:
stack.append((j + 1, hi))
hi = j
else:
stack.append((lo, j))
lo = j + 1
test_hoare_partition.py 56 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/hoare-partition/. The authors are listed in prov/HR9MYC.jsonl.
import itertools
import random
from hoare_partition import hoare_partition, quicksort
def check(a: list[int], lo: int, hi: int) -> None:
before = list(a)
j = hoare_partition(a, lo, hi)
assert lo <= j < hi
assert max(a[lo : j + 1]) <= min(a[j + 1 : hi + 1])
assert sorted(a[lo : hi + 1]) == sorted(before[lo : hi + 1])
assert a[:lo] == before[:lo] and a[hi + 1 :] == before[hi + 1 :]
def test_example() -> None:
a = [5, 3, 8, 4, 9, 2, 7, 1, 6]
assert hoare_partition(a, 0, 8) == 3
assert a == [1, 3, 2, 4, 9, 8, 7, 5, 6]
def test_edges() -> None:
a = [2, 1]
assert hoare_partition(a, 0, 1) == 0 and a == [1, 2]
a = [1, 2]
assert hoare_partition(a, 0, 1) == 0 and a == [1, 2]
a = [7] * 8
assert hoare_partition(a, 0, 7) == 3
a = [7] * 9
assert hoare_partition(a, 0, 8) == 4
check([9, 1, 2, 3, 4], 0, 4)
check([1, 9, 8, 7], 0, 3)
check([0, 5, 3, 5, 1, 0], 1, 4)
def test_all_permutations() -> None:
for n in range(2, 8):
for p in itertools.permutations(range(n)):
check(list(p), 0, n - 1)
def test_random_partitions_and_sort() -> None:
rng = random.Random(1961)
for _ in range(800):
n = rng.randint(2, 40)
a = [rng.randint(-5, 5) for _ in range(n)]
lo = rng.randint(0, n - 2)
hi = rng.randint(lo + 1, n - 1)
check(a, lo, hi)
b = [rng.randint(-100, 100) for _ in range(rng.randint(0, 60))]
c = list(b)
quicksort(c)
assert c == sorted(b)
What the next level needs
- the tests did not run in this build