Shearsort in Python
Mesh sort that alternates sorting rows in snake order and columns, in O(log n) phases.
- File
shearsort.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/shearsort/. The authors are listed in prov/YNCX5H.jsonl.
"""Shearsort on an r by c mesh, into snake order.
Rows and columns are sorted by odd-even transposition sort, so every
step is a set of compare-exchanges between neighbours. The code runs
the rows (or the columns) of one step one after the other, which gives
the same result as running them at the same time.
"""
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def oets_line(line: list[T], ascending: bool) -> int:
"""Sort line in place by odd-even transposition. Return the number of rounds."""
n = len(line)
for t in range(n):
for i in range(t % 2, n - 1, 2):
a, b = line[i], line[i + 1]
if (b < a) if ascending else (a < b):
line[i], line[i + 1] = b, a
return n
def sort_rows(m: list[list[T]]) -> int:
"""Sort even rows ascending and odd rows descending. Return the steps."""
steps = 0
for i, row in enumerate(m): # @line L2
steps = max(steps, oets_line(row, i % 2 == 0)) # @line L3
return steps
def sort_columns(m: list[list[T]]) -> int:
"""Sort every column ascending from top to bottom. Return the steps."""
r, c = len(m), len(m[0])
for j in range(c): # @line L4
col = [m[i][j] for i in range(r)]
oets_line(col, True) # @line L5
for i in range(r):
m[i][j] = col[i]
return r
def shearsort(m: list[list[T]]) -> int:
"""Sort the matrix m in place into snake order. Return the number of steps."""
if not m or not m[0]:
return 0
r = len(m)
phases = (r - 1).bit_length() # the value of ceil(lg r)
steps = 0
for _ in range(phases): # @line L1
steps += sort_rows(m)
steps += sort_columns(m)
steps += sort_rows(m) # @line L6
return steps
def snake(m: list[list[T]]) -> list[T]:
"""Read the matrix in snake order."""
out: list[T] = []
for i, row in enumerate(m):
out.extend(row if i % 2 == 0 else reversed(row))
return out
test_shearsort.py 49 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/shearsort/. The authors are listed in prov/YNCX5H.jsonl.
import itertools
import random
from shearsort import shearsort, snake
def grid(values: list[int], c: int) -> list[list[int]]:
return [values[i : i + c] for i in range(0, len(values), c)]
def test_example() -> None:
m = [[13, 2, 7, 10], [5, 16, 1, 12], [9, 4, 15, 8], [3, 14, 6, 11]]
steps = shearsort(m)
assert m == [[1, 2, 3, 4], [8, 7, 6, 5], [9, 10, 11, 12], [16, 15, 14, 13]]
assert steps == 2 * (4 + 4) + 4
def test_two_by_two() -> None:
m = [[4, 1], [3, 2]]
shearsort(m)
assert m == [[1, 2], [4, 3]]
def test_all_zero_one_inputs() -> None:
for r, c in ((1, 5), (2, 3), (3, 3), (3, 4), (4, 3), (2, 5), (5, 2)):
for bits in itertools.product((0, 1), repeat=r * c):
m = grid(list(bits), c)
shearsort(m)
assert snake(m) == sorted(bits)
def test_step_count_square() -> None:
for side in (2, 4, 8, 16):
m = [[0] * side for _ in range(side)]
n = side * side
assert shearsort(m) == side * (n.bit_length() - 1 + 1)
def test_random_against_sorted() -> None:
rng = random.Random(6)
for _ in range(200):
r, c = rng.randint(1, 7), rng.randint(1, 7)
vals = [rng.randint(0, 30) for _ in range(r * c)]
m = grid(vals, c)
shearsort(m)
assert snake(m) == sorted(vals)
What the next level needs
- the tests did not run in this build