Pancake sort in Python
Sorts by repeatedly reversing prefixes, using at most about 2n reversals.
- File
pancake_sort.py, 41 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/pancake-sort/. The authors are listed in prov/NCD5YW.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def flip(a: list[T], m: int) -> None:
"""Reverse the prefix a[0:m + 1]."""
i, j = 0, m
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
def pancake_sort(a: list[T], flips: list[int] | None = None) -> None:
"""Sort a in place by prefix reversals only.
If flips is a list, the size of each reversed prefix is appended to it, in order.
"""
n = len(a)
for k in range(n, 1, -1): # @line L1
m = 0 # @line L2: the index of the first largest item of a[0:k]
for j in range(1, k):
if a[m] < a[j]:
m = j
if m != k - 1: # @line L3
if m != 0: # @line L4
flip(a, m)
if flips is not None:
flips.append(m + 1)
flip(a, k - 1) # @line L5
if flips is not None:
flips.append(k)
test_pancake_sort.py 61 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/pancake-sort/. The authors are listed in prov/NCD5YW.jsonl.
import itertools
import random
from pancake_sort import flip, pancake_sort
def test_example() -> None:
a = [3, 6, 1, 5, 2, 4]
flips: list[int] = []
pancake_sort(a, flips)
assert a == [1, 2, 3, 4, 5, 6]
assert flips == [2, 6, 3, 5, 3, 4, 2, 3]
def test_flip() -> None:
a = [1, 2, 3, 4, 5]
flip(a, 2)
assert a == [3, 2, 1, 4, 5]
flip(a, 0)
assert a == [3, 2, 1, 4, 5]
def test_flips_replay() -> None:
# Only prefix reversals are used: replaying the recorded flips sorts a copy.
rng = random.Random(6)
for _ in range(200):
a = [rng.randint(0, 9) for _ in range(rng.randint(0, 30))]
b = list(a)
flips: list[int] = []
pancake_sort(b, flips)
assert b == sorted(a)
for size in flips:
a[:size] = a[:size][::-1]
assert a == b
def test_at_most_2n_minus_3_flips() -> None:
for n in range(2, 8):
for p in itertools.permutations(range(n)):
a = list(p)
flips: list[int] = []
pancake_sort(a, flips)
assert a == list(range(n))
assert len(flips) <= 2 * n - 3
def test_edges() -> None:
for a in ([], [1], [1, 1], [2, 1], [5, 5, 1]):
b = list(a)
pancake_sort(b)
assert b == sorted(a)
def test_sorted_needs_no_flip() -> None:
a = list(range(100))
flips: list[int] = []
pancake_sort(a, flips)
assert flips == []
What the next level needs
- the tests did not run in this build