Cocktail shaker sort in Python
Bubble sort that alternates passes in both directions.
- File
cocktail_shaker_sort.py, 38 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/cocktail-shaker-sort/. The authors are listed in prov/9RXP2E.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def cocktail_shaker_sort(a: list[T]) -> int:
"""Sort a in place, in non-decreasing order, and return the number of rounds.
A round is a pass to the right and a pass to the left over the unsorted
part a[lo..hi]. Each pass stops at the place of the last exchange of the
pass before. The sort is stable.
Cost: exactly d exchanges and O(n^2) comparisons, d = inversions.
"""
rounds = 0
lo, hi = 0, len(a) - 1 # @line L1
while lo < hi: # @line L2
rounds += 1
last = lo # @line L3
for j in range(lo, hi): # @line L4
if a[j + 1] < a[j]: # @line L5: a[j] > a[j + 1]
a[j], a[j + 1] = a[j + 1], a[j] # @line L6
last = j
hi = last # @line L7
last = hi # @line L8
for j in range(hi - 1, lo - 1, -1): # @line L9
if a[j + 1] < a[j]: # @line L10: a[j] > a[j + 1]
a[j], a[j + 1] = a[j + 1], a[j] # @line L11
last = j + 1
lo = last # @line L12
return rounds
test_cocktail_shaker_sort.py 64 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/cocktail-shaker-sort/. The authors are listed in prov/9RXP2E.jsonl.
import itertools
import random
from cocktail_shaker_sort import cocktail_shaker_sort
def test_example() -> None:
a = [5, 1, 4, 2, 8, 0, 3]
assert cocktail_shaker_sort(a) == 2
assert a == [0, 1, 2, 3, 4, 5, 8]
def test_small_item_at_the_end() -> None:
a = [2, 3, 4, 5, 6, 1]
assert cocktail_shaker_sort(a) == 2
assert a == [1, 2, 3, 4, 5, 6]
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 2], [1, 1, 1], [3, 2, 1], [2**63 - 1, -(2**63)]):
b = list(a)
cocktail_shaker_sort(b)
assert b == sorted(a)
def test_sorted_input_takes_one_round() -> None:
a = list(range(20))
assert cocktail_shaker_sort(a) == 1
def test_all_permutations_and_rounds_bound() -> None:
for n in range(1, 7):
for p in itertools.permutations(range(n)):
big = max(sum(1 for i in range(p.index(v)) if p[i] > v) for v in p)
small = max(sum(1 for i in range(p.index(v) + 1, n) if p[i] < v) for v in p)
b = list(p)
rounds = cocktail_shaker_sort(b)
assert b == list(range(n))
assert rounds <= min(big, small) + 1
def test_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(2, "a"), Key(1, "b"), Key(2, "c"), Key(1, "d")]
cocktail_shaker_sort(a)
assert [x.tag for x in a] == ["b", "d", "a", "c"]
def test_random_against_sorted() -> None:
rng = random.Random(5222)
for _ in range(600):
a = [rng.randint(-30, 30) for _ in range(rng.randint(0, 50))]
b = list(a)
cocktail_shaker_sort(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build