Comb sort in Python

Bubble sort generalized to compare elements a shrinking gap apart, removing small values near the end quickly.

File: comb_sort.py, 35 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/comb-sort/. The authors are listed in prov/SYZVMD.jsonl.

from typing import Protocol, TypeVar


class Ordered(Protocol):
    def __lt__(self, other: "Ordered", /) -> bool: ...


T = TypeVar("T", bound=Ordered)


def comb_sort(a: list[T]) -> int:
    """Sort a in place, in non-decreasing order, and return the number of passes.

    Each pass compares the items a gap apart and exchanges the pairs that are
    out of order. The gap shrinks by the factor 1.3 down to 1, in integer
    arithmetic as gap * 10 // 13. Passes with gap 1 go on until one makes no
    exchange. The sort is not stable.
    Cost: O(n^2) comparisons in the worst case, about n lg n on random input.
    """
    n = len(a)
    passes = 0
    gap = n  # @line L1
    done = False  # @line L2
    while not done:  # @line L3
        passes += 1
        gap = max(1, gap * 10 // 13)  # @line L4
        done = gap == 1  # @line L5
        for i in range(n - gap):  # @line L6
            if a[i + gap] < a[i]:  # @line L7: a[i] > a[i + gap]
                a[i], a[i + gap] = a[i + gap], a[i]  # @line L8
                done = False  # @line L9
    return passes

test_comb_sort.py 47 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/comb-sort/. The authors are listed in prov/SYZVMD.jsonl.

import itertools
import random

from comb_sort import comb_sort


def test_example() -> None:
    a = [8, 4, 1, 5, 9, 2, 6, 3, 7, 0]
    assert comb_sort(a) == 6
    assert a == list(range(10))


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)
        comb_sort(b)
        assert b == sorted(a)


def test_all_permutations() -> None:
    for n in range(1, 8):
        for p in itertools.permutations(range(n)):
            b = list(p)
            comb_sort(b)
            assert b == list(range(n))


def test_gap_sequence_on_sorted_input() -> None:
    # 1000 -> 769 -> 591 -> ... -> 1: the passes before gap 1, then one pass with gap 1.
    gaps = []
    g = 1000
    while g > 1:
        g = max(1, g * 10 // 13)
        gaps.append(g)
    assert comb_sort(list(range(1000))) == len(gaps)


def test_random_against_sorted() -> None:
    rng = random.Random(1980)
    for _ in range(600):
        a = [rng.randint(-30, 30) for _ in range(rng.randint(0, 60))]
        b = list(a)
        comb_sort(b)
        assert b == sorted(a)

What the next level needs

the tests did not run in this build

Read the full page about Comb sort