Multikey quicksort in Python
Three-way quicksort on the current character of each string, recursing on the next character for equal keys.
- File
multikey_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/multikey-quicksort/. The authors are listed in prov/36KMJW.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 multikey_quicksort(a: list[str], seed: int | None = None) -> list[str]:
"""Sort the list a of strings in lexicographic order, in place, and return it.
Precondition: the items are str. The sort is not stable.
The expected cost is O(n log n + D) character reads, where D is the total
length of the distinguishing prefixes; the extra space is the task stack.
"""
rng = random.Random(seed)
stack = [(0, len(a), 0)] # @line L1
while stack: # @line L2
lo, hi, d = stack.pop() # @line L3
if hi - lo <= 1: # @line L4
continue
v = _c(a[rng.randrange(lo, hi)], d) # @line L5
lt, i, gt = lo, lo, hi - 1 # @line L6
while i <= gt:
x = _c(a[i], d)
if x < v:
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif x > v:
a[i], a[gt] = a[gt], a[i]
gt -= 1
else:
i += 1
gt += 1
stack.append((gt, hi, d)) # @line L7
if v != -1: # @line L8
stack.append((lt, gt, d + 1))
stack.append((lo, lt, d)) # @line L9
return a # @line L10
test_multikey_quicksort.py 49 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/multikey-quicksort/. The authors are listed in prov/36KMJW.jsonl.
import random
import unittest
from multikey_quicksort import multikey_quicksort
class TestMultikeyQuicksort(unittest.TestCase):
def test_page_example(self):
a = "she sells sea shells by the sea shore".split()
self.assertEqual(
multikey_quicksort(a, seed=1),
["by", "sea", "sea", "sells", "she", "shells", "shore", "the"],
)
def test_in_place(self):
a = ["b", "a"]
r = multikey_quicksort(a)
self.assertIs(r, a)
self.assertEqual(a, ["a", "b"])
def test_edges(self):
self.assertEqual(multikey_quicksort([]), [])
self.assertEqual(multikey_quicksort(["x"]), ["x"])
self.assertEqual(multikey_quicksort(["", "a", ""]), ["", "", "a"])
self.assertEqual(multikey_quicksort(["ab", "a", "abc", "b"]), ["a", "ab", "abc", "b"])
self.assertEqual(multikey_quicksort(["aaa"] * 5), ["aaa"] * 5)
def test_unicode(self):
a = ["été", "zebra", "中文", "apple", "é"]
self.assertEqual(multikey_quicksort(a), sorted(a))
def test_long_common_prefix(self):
p = "x" * 5000
a = [p + "b", p, p + "a", p + "ab"]
self.assertEqual(multikey_quicksort(a), sorted(a))
def test_random(self):
rng = random.Random(36)
for _ in range(600):
n = rng.randint(0, 40)
k = rng.choice([1, 2, 3, 26])
a = ["".join(chr(97 + rng.randrange(k)) for _ in range(rng.randint(0, 6))) for _ in range(n)]
self.assertEqual(multikey_quicksort(list(a), 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