Gnome sort in Python
Moves one element backward by adjacent swaps until ordered, then steps forward; equivalent in cost to insertion sort.
- File
gnome_sort.py, 31 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/gnome-sort/. The authors are listed in prov/6HS4Z7.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def gnome_sort(a: list[T]) -> int:
"""Sort a in place, in non-decreasing order, and return the number of steps.
One index walks forward while its item is in order with the item to its
left, and otherwise exchanges the two and steps back. The sort is stable.
Cost: exactly n + 2d steps and d exchanges, d = inversions.
"""
n = len(a)
steps = 0
i = 0 # @line L1
while i < n: # @line L2
steps += 1
if i == 0 or not a[i] < a[i - 1]: # @line L3: i = 0 or a[i - 1] <= a[i]
i += 1 # @line L4
else: # @line L5
a[i - 1], a[i] = a[i], a[i - 1] # @line L6
i -= 1 # @line L7
return steps
test_gnome_sort.py 54 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/gnome-sort/. The authors are listed in prov/6HS4Z7.jsonl.
import itertools
import random
from gnome_sort import gnome_sort
def inversions(a: list[int]) -> int:
return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] > a[j])
def test_example() -> None:
a = [3, 1, 4, 2]
assert gnome_sort(a) == 10
assert a == [1, 2, 3, 4]
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)
gnome_sort(b)
assert b == sorted(a)
def test_steps_are_n_plus_2d() -> None:
for n in range(0, 7):
for p in itertools.permutations(range(n)):
b = list(p)
assert gnome_sort(b) == n + 2 * inversions(list(p))
assert b == list(range(n))
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")]
gnome_sort(a)
assert [x.tag for x in a] == ["b", "d", "a", "c"]
def test_random_against_sorted() -> None:
rng = random.Random(2000)
for _ in range(600):
a = [rng.randint(-30, 30) for _ in range(rng.randint(0, 50))]
b = list(a)
gnome_sort(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build