Proxmap sort in Python
Distribution sort that uses a proximity map from key values to array slots, with insertion to fix local order.
- File
proxmap_sort.py, 84 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/proxmap-sort/. The authors are listed in prov/QTZM0Z.jsonl.
from typing import Callable, Union
Key = Union[int, float, str]
def _common_prefix(s: str, t: str) -> int:
p = 0
while p < len(s) and p < len(t) and s[p] == t[p]:
p += 1
return p
def map_key(a: list[Key], lo: Key, hi: Key, m: int) -> Callable[[Key], int]:
"""Return a non-decreasing map from the keys of a onto 0 .. m - 1, with K(lo) = 0 and K(hi) = m - 1.
Integers use exact arithmetic, floats use (x - lo) / (hi - lo) with a
clamp, and strings use a code of four characters after the common
prefix of lo and hi. Precondition: lo < hi are the extremes of a.
"""
if isinstance(lo, str):
p = _common_prefix(lo, hi) # type: ignore[arg-type]
base = 2 + max(ord(c) for s in a for c in s[p:p + 4]) # type: ignore[union-attr]
def code(s: str) -> int:
v = 0
for t in range(p, p + 4):
v = v * base + (ord(s[t]) + 1 if t < len(s) else 0)
return v
clo, chi = code(lo), code(hi) # type: ignore[arg-type]
return lambda s: (m - 1) * (code(s) - clo) // (chi - clo) # type: ignore[arg-type]
if isinstance(lo, int) and isinstance(hi, int) and all(isinstance(x, int) for x in a):
span = hi - lo
return lambda x: (m - 1) * (x - lo) // span # type: ignore[operator]
flo, fhi = float(lo) / 2, float(hi) / 2 # halves avoid overflow of hi - lo
fspan = fhi - flo
return lambda x: min(m - 1, max(0, int((float(x) / 2 - flo) / fspan * (m - 1))))
def proxmap_sort(a: list[Key], m: int | None = None, key_map: Callable[[Key], int] | None = None) -> None:
"""Sort the list a in place, in non-decreasing order. The sort is stable.
Precondition: the keys are all numbers or all strings; key_map, if given,
is non-decreasing with values in 0 .. m - 1. By default m = n and the map
is linear from the minimum to the maximum. The cost is Theta(n) expected
time for keys spread evenly, Theta(n^2) in the worst case, and
Theta(n + m) extra space.
"""
n = len(a)
if n <= 1:
return
if m is None:
m = n
if m < 1:
raise ValueError("m must be at least 1")
if key_map is None:
lo, hi = min(a), max(a)
if not lo < hi: # type: ignore[operator]
return
key_map = map_key(a, lo, hi, m) if m >= 2 else (lambda x: 0)
M = key_map
h = [0] * m # @line L1
for x in a:
h[M(x)] += 1
p = [0] * m # @line L2
s = 0
for k in range(m):
p[k] = s
s += h[k]
f = [0] * m # @line L3
b: list[Key] = [None] * n # type: ignore[list-item]
for i in range(n): # @line L4
x = a[i] # @line L5
k = M(x)
j = p[k] + f[k]
f[k] += 1
while j > p[k] and b[j - 1] > x: # @line L6
b[j] = b[j - 1]
j -= 1
b[j] = x # @line L7
a[:] = b # @line L8
return # @line L9
test_proxmap_sort.py 67 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/proxmap-sort/. The authors are listed in prov/QTZM0Z.jsonl.
import math
import random
import unittest
from proxmap_sort import proxmap_sort
class TestProxmapSort(unittest.TestCase):
def test_page_example(self):
a = [3.4, 0.9, 5.2, 3.1, 7.7, 0.2, 5.9, 3.8, 2.5, 6.0]
proxmap_sort(a, m=8, key_map=math.floor)
self.assertEqual(a, [0.2, 0.9, 2.5, 3.1, 3.4, 3.8, 5.2, 5.9, 6.0, 7.7])
def test_default_map(self):
a = [3.4, 0.9, 5.2, 3.1, 7.7, 0.2, 5.9, 3.8, 2.5, 6.0]
b = list(a)
proxmap_sort(b)
self.assertEqual(b, sorted(a))
def test_edges(self):
for a in ([], [1], [2, 1], [4, 4, 4], [0, -5, 3, -1, -5, 2], [2**63 - 1, -(2**63), 0, 2**63 - 1]):
b = list(a)
proxmap_sort(b)
self.assertEqual(b, sorted(a))
with self.assertRaises(ValueError):
proxmap_sort([2, 1], m=0)
def test_strings(self):
for a in (["pear", "fig", "apple"], ["b", "", "a", "ab", ""], ["same"] * 4, ["zzzzzzb", "zzzzzz", "zzzzzza"]):
b = list(a)
proxmap_sort(b)
self.assertEqual(b, sorted(a))
def test_stable(self):
a = [(2, "a"), (1, "b"), (2, "c"), (1, "d")]
keys = [p[0] for p in a]
order = list(range(len(a)))
# sort indices by key with a map on the key value; ties keep input order
idx = [k * 10 + i for i, k in enumerate(keys)]
proxmap_sort(idx, m=3, key_map=lambda v: v // 10)
self.assertEqual([order[v % 10] for v in idx], [1, 3, 0, 2])
def test_one_subarray(self):
a = list(range(200, 0, -1))
proxmap_sort(a, m=1)
self.assertEqual(a, list(range(1, 201)))
def test_random(self):
rng = random.Random(1998)
for _ in range(600):
n = rng.randint(0, 80)
kind = rng.randrange(3)
if kind == 0:
a = [rng.randint(-50, 50) for _ in range(n)]
elif kind == 1:
a = [rng.random() * 100 for _ in range(n)]
else:
a = ["".join(rng.choice("xyz") for _ in range(rng.randint(0, 4))) for _ in range(n)]
b = list(a)
proxmap_sort(b, m=rng.choice([None, 1, 2, 7]))
self.assertEqual(b, sorted(a))
if __name__ == "__main__":
unittest.main()
What the next level needs
- the tests did not run in this build