Cycle sort in Python
In-place sort that writes each element to its final position exactly once, minimizing the number of writes.
- File
cycle_sort.py, 51 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/cycle-sort/. The authors are listed in prov/FAY1AX.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def _position(a: list[T], s: int, x: T) -> int:
p = s # @line L13
for i in range(s + 1, len(a)): # @line L14
if a[i] < x: # @line L15
p += 1
return p # @line L16
def _equal(x: T, y: T) -> bool:
return not x < y and not y < x
def cycle_sort(a: list[T]) -> int:
"""Sort a in place, in non-decreasing order, and return the number of writes.
Each start position s takes its item x, counts the items to its right that
are smaller to find the final place of x, and follows the cycle of the
permutation from there until an item lands at s. Each array write puts an
item at its final place, so the number of writes is the number of
positions whose item must change, which is the least possible.
Cost: Θ(n²) comparisons on every input, Θ(1) extra space.
"""
n = len(a)
writes = 0 # @line L1
for s in range(n - 1): # @line L2
x = a[s] # @line L3
p = _position(a, s, x) # @line L4
if p == s: # @line L5
continue
while True: # @line L6
while _equal(x, a[p]): # @line L7
p += 1
a[p], x = x, a[p] # @line L8
writes += 1 # @line L9
if p == s: # @line L10
break
p = _position(a, s, x) # @line L11
return writes # @line L12
test_cycle_sort.py 84 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/cycle-sort/. The authors are listed in prov/FAY1AX.jsonl.
import itertools
import random
from cycle_sort import cycle_sort
def misplaced(a: list[int]) -> int:
s = sorted(a)
return sum(1 for x, y in zip(a, s) if x != y)
def test_example() -> None:
a = [3, 0, 4, 1, 2]
assert cycle_sort(a) == 5
assert a == [0, 1, 2, 3, 4]
def test_example_with_duplicates() -> None:
a = [2, 4, 1, 2, 0, 4]
assert cycle_sort(a) == 4
assert a == [0, 1, 2, 2, 4, 4]
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 2], [1, 1, 1], [3, 2, 1], [2**63 - 1, -(2**63)], [2**63 - 1, 0, -(2**63), 2**63 - 1]):
b = list(a)
cycle_sort(b)
assert b == sorted(a)
def test_sorted_input_has_no_writes() -> None:
a = list(range(50))
assert cycle_sort(a) == 0
assert a == list(range(50))
def test_writes_are_minimal_on_permutations() -> None:
for n in range(0, 7):
for p in itertools.permutations(range(n)):
b = list(p)
fixed = sum(1 for i in range(n) if p[i] == i)
assert cycle_sort(b) == n - fixed
assert b == list(range(n))
def test_writes_are_minimal_with_duplicates() -> None:
rng = random.Random(7)
for _ in range(600):
a = [rng.randint(0, 4) for _ in range(rng.randint(0, 14))]
b = list(a)
assert cycle_sort(b) == misplaced(a)
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(1, "a"), Key(1, "b"), Key(0, "c")]
cycle_sort(a)
assert [x.k for x in a] == [0, 1, 1]
assert [x.tag for x in a] == ["c", "b", "a"]
def test_random_against_sorted() -> None:
rng = random.Random(1990)
for _ in range(600):
a = [rng.randint(-30, 30) for _ in range(rng.randint(0, 50))]
b = list(a)
cycle_sort(b)
assert b == sorted(a)
def test_strings() -> None:
a = ["pear", "fig", "apple", "fig", "kiwi"]
cycle_sort(a)
assert a == ["apple", "fig", "fig", "kiwi", "pear"]
What the next level needs
- the tests did not run in this build