Three-way radix quicksort in Python
String sort that partitions on the leading character into three parts and recurses, combining quicksort and most-significant-digit radix sort.
- File
three_way_radix_quicksort.py, 57 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/three-way-radix-quicksort/. The authors are listed in prov/PC1TJR.jsonl.
import random
def _c(s: str, d: int) -> int:
"""The character code of s at index d, or -1 when s has ended."""
return ord(s[d]) if d < len(s) else -1
def _insertion_sort(a: list[str], lo: int, hi: int, d: int) -> None:
"""Sort a[lo:hi] by the suffixes from index d; the strings share d characters."""
for i in range(lo + 1, hi):
x = a[i]
j = i
while j > lo and x[d:] < a[j - 1][d:]:
a[j] = a[j - 1]
j -= 1
a[j] = x
def _sort(a: list[str], lo: int, hi: int, d: int, m: int) -> None:
while hi - lo > m: # @line L1
v = _c(a[lo], d) # @line L2
lt, gt, i = lo, hi - 1, lo + 1 # @line L3
while i <= gt: # @line L4
t = _c(a[i], d) # @line L5
if t < v: # @line L6
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif t > v: # @line L7
a[i], a[gt] = a[gt], a[i]
gt -= 1
else: # @line L8
i += 1
_sort(a, lo, lt, d, m) # @line L9
_sort(a, gt + 1, hi, d, m) # @line L10
if v == -1: # @line L11
return
lo, hi, d = lt, gt + 1, d + 1 # @line L12
_insertion_sort(a, lo, hi, d) # @line L13
def three_way_radix_quicksort(a: list[str], cutoff: int = 15, seed: int | None = None, shuffle: bool = True) -> list[str]:
"""Sort the list a of strings in lexicographic order, in place, and return it.
Precondition: the items are str and cutoff >= 1. The sort is not stable.
After the shuffle the expected cost is O(n log n + D) character reads,
where D is the total length of the distinguishing prefixes.
"""
if cutoff < 1:
raise ValueError("cutoff must be at least 1")
if shuffle:
random.Random(seed).shuffle(a)
_sort(a, 0, len(a), 0, cutoff)
return a
test_three_way_radix_quicksort.py 50 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/three-way-radix-quicksort/. The authors are listed in prov/PC1TJR.jsonl.
import random
import unittest
from three_way_radix_quicksort import three_way_radix_quicksort
class TestThreeWayRadixQuicksort(unittest.TestCase):
def test_page_example(self):
a = ["cab", "add", "dad", "bad", "cad", "ace", "ad"]
want = ["ace", "ad", "add", "bad", "cab", "cad", "dad"]
self.assertEqual(three_way_radix_quicksort(list(a), cutoff=1, shuffle=False), want)
self.assertEqual(three_way_radix_quicksort(list(a)), want)
def test_in_place(self):
a = ["b", "a", "c"]
self.assertIs(three_way_radix_quicksort(a, cutoff=1), a)
self.assertEqual(a, ["a", "b", "c"])
def test_edges(self):
self.assertEqual(three_way_radix_quicksort([]), [])
self.assertEqual(three_way_radix_quicksort([""]), [""])
self.assertEqual(three_way_radix_quicksort(["", "a", ""], cutoff=1), ["", "", "a"])
self.assertEqual(three_way_radix_quicksort(["ab", "b", "abc", "a", "ba"], cutoff=1), ["a", "ab", "abc", "b", "ba"])
self.assertEqual(three_way_radix_quicksort(["zz"] * 40, cutoff=1), ["zz"] * 40)
with self.assertRaises(ValueError):
three_way_radix_quicksort(["a"], cutoff=0)
def test_long_common_prefix(self):
p = "q" * 5000
a = [p + "c", p, p + "a", p + "ab", p + "b"]
self.assertEqual(three_way_radix_quicksort(a, cutoff=1), sorted(a))
def test_unicode(self):
a = ["ñu", "nu", "中", "", "Zeta", "zeta"]
self.assertEqual(three_way_radix_quicksort(list(a), cutoff=1), sorted(a))
def test_random(self):
rng = random.Random(1997)
for _ in range(600):
n = rng.randint(0, 60)
k = rng.choice([1, 2, 4, 26])
a = ["".join(chr(97 + rng.randrange(k)) for _ in range(rng.randint(0, 7))) for _ in range(n)]
m = rng.choice([1, 2, 15])
self.assertEqual(three_way_radix_quicksort(list(a), cutoff=m, seed=rng.randrange(10**6)), sorted(a))
if __name__ == "__main__":
unittest.main()
What the next level needs
- the tests did not run in this build