Dual-pivot quicksort in Python
Quicksort partitioning around two pivots into three ranges; the default for Java primitive arrays.
- File
dual_pivot_quicksort.py, 71 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/dual-pivot-quicksort/. The authors are listed in prov/8SHK9M.jsonl.
import random
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def dual_pivot_quicksort(a: list[T], seed: int = 2009) -> None:
"""Sort a in place, in non-decreasing order.
Yaroslavskiy's partition splits each range around two pivots p <= q into
the items less than p, the items between p and q, and the items greater
than q, and the three parts are sorted recursively. The pivots are two
random items of the range. Not stable.
Cost: expected 1.9 n ln n - 2.46 n + O(log n) comparisons on a random
permutation (Wild and Nebel), Θ(n²) in the worst case, O(log n) expected
stack depth.
"""
_sort(a, 0, len(a) - 1, random.Random(seed))
def _sort(a: list[T], lo: int, hi: int, rng: random.Random) -> None:
if hi <= lo: # @line L1
return
r = rng.randint(lo, hi) # @line L2: random pivots to the two ends
a[lo], a[r] = a[r], a[lo]
r = rng.randint(lo + 1, hi)
a[hi], a[r] = a[r], a[hi]
l, g = partition(a, lo, hi) # @line L3
_sort(a, lo, l - 1, rng) # @line L4
_sort(a, l + 1, g - 1, rng) # @line L5
_sort(a, g + 1, hi, rng) # @line L6
def partition(a: list[T], lo: int, hi: int) -> tuple[int, int]:
"""Partition a[lo..hi] (lo < hi) around p = min and q = max of the end items.
Return (l, g) with a[l] = p, a[g] = q, a[lo..l-1] < p, p <= a[l+1..g-1] <= q
and a[g+1..hi] >= q.
"""
if a[hi] < a[lo]: # @line L7
a[lo], a[hi] = a[hi], a[lo]
p, q = a[lo], a[hi] # @line L8
l = lo + 1 # @line L9
g = hi - 1
k = l
while k <= g: # @line L10
if a[k] < p: # @line L11
a[k], a[l] = a[l], a[k] # @line L12
l += 1
elif not a[k] < q: # @line L13: a[k] >= q
while q < a[g] and k < g: # @line L14
g -= 1
a[k], a[g] = a[g], a[k] # @line L15
g -= 1
if a[k] < p: # @line L16
a[k], a[l] = a[l], a[k] # @line L17
l += 1
k += 1 # @line L18
l -= 1 # @line L19
g += 1
a[lo], a[l] = a[l], a[lo] # @line L20
a[hi], a[g] = a[g], a[hi]
return l, g # @line L21
test_dual_pivot_quicksort.py 96 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/dual-pivot-quicksort/. The authors are listed in prov/8SHK9M.jsonl.
import itertools
import random
from dual_pivot_quicksort import dual_pivot_quicksort, partition
class Counted:
count = 0
def __init__(self, k: int) -> None:
self.k = k
def __lt__(self, other: "Counted") -> bool:
Counted.count += 1
return self.k < other.k
def test_example_partition() -> None:
a = [Counted(x) for x in [3, 7, 1, 8, 5, 2, 9, 4, 6]]
Counted.count = 0
assert partition(a, 0, 8) == (2, 5)
assert [x.k for x in a] == [2, 1, 3, 4, 5, 6, 9, 7, 8]
assert Counted.count == 13
def test_example_sort() -> None:
a = [3, 7, 1, 8, 5, 2, 9, 4, 6]
dual_pivot_quicksort(a)
assert a == list(range(1, 10))
def test_partition_postcondition() -> None:
for n in range(2, 8):
for p in itertools.product(range(4), repeat=n):
a = list(p)
l, g = partition(a, 0, n - 1)
x, y = a[l], a[g]
assert 0 <= l < g <= n - 1
assert sorted(a) == sorted(p)
assert all(v < x for v in a[:l])
assert all(x <= v <= y for v in a[l + 1 : g])
assert all(v >= y for v in a[g + 1 :])
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 2], [1, 1, 1], [3, 2, 1], [2**63 - 1, -(2**63)], [0, 2**63 - 1, -(2**63), 0]):
b = list(a)
dual_pivot_quicksort(b)
assert b == sorted(a)
def test_all_small_permutations() -> None:
for n in range(0, 8):
for p in itertools.permutations(range(n)):
b = list(p)
dual_pivot_quicksort(b)
assert b == list(range(n))
def test_sorted_equal_and_reversed_large() -> None:
for a in (list(range(3000)), [5] * 3000, list(range(3000, 0, -1))):
b = list(a)
dual_pivot_quicksort(b)
assert b == sorted(a)
def test_not_stable() -> None:
class Key:
def __init__(self, k: int, tag: str) -> None:
self.k, self.tag = k, tag
def __lt__(self, other: "Key") -> bool:
return self.k < other.k
a = [Key(0, "a"), Key(1, "b"), Key(1, "c"), Key(0, "d")]
partition(a, 0, 3)
assert [x.k for x in a] == [0, 0, 1, 1]
assert [x.tag for x in a] == ["a", "d", "c", "b"]
def test_random_against_sorted() -> None:
rng = random.Random(2012)
for _ in range(600):
a = [rng.randint(-30, 30) for _ in range(rng.randint(0, 60))]
b = list(a)
dual_pivot_quicksort(b, seed=rng.randrange(1000))
assert b == sorted(a)
def test_strings() -> None:
a = ["pear", "fig", "apple", "fig", "kiwi"]
dual_pivot_quicksort(a)
assert a == ["apple", "fig", "fig", "kiwi", "pear"]
What the next level needs
- the tests did not run in this build