Bogosort in Python

Randomly permutes the array until sorted; expected factorial time, included as a pedagogical counterexample.

File: bogosort.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/bogosort/. The authors are listed in prov/YA1S1T.jsonl.

import random
from typing import Protocol, TypeVar


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


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


def bogosort(a: list[T], rng: random.Random | None = None) -> int:
    """Sort a in place by shuffling it until it is sorted; return the number of shuffles.

    The result is always sorted. On n distinct keys that are not sorted, the
    expected number of shuffles is n!, so use it only on very small lists.
    """
    rng = rng if rng is not None else random.Random()
    shuffles = 0
    while not is_sorted(a):  # @line L1
        shuffle(a, rng)  # @line L2
        shuffles += 1
    return shuffles


def is_sorted(a: list[T]) -> bool:
    """Return True when a is in non-decreasing order. At most len(a) - 1 comparisons."""
    for i in range(1, len(a)):  # @line L3
        if a[i] < a[i - 1]:  # @line L4: a[i - 1] > a[i]
            return False
    return True  # @line L5


def shuffle(a: list[T], rng: random.Random) -> None:
    """Put a in a uniformly random order with the Fisher-Yates shuffle."""
    for i in range(len(a) - 1, 0, -1):  # @line L6
        j = rng.randint(0, i)  # @line L7
        a[i], a[j] = a[j], a[i]  # @line L8

test_bogosort.py 57 lines

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

import itertools
import random
from collections import Counter

from bogosort import bogosort, is_sorted, shuffle


def test_example() -> None:
    a = [3, 1, 2]
    bogosort(a, random.Random(3))
    assert a == [1, 2, 3]


def test_edges() -> None:
    rng = random.Random(0)
    for a in ([], [1], [1, 2, 3], [2, 2, 2]):
        b = list(a)
        assert bogosort(b, rng) == 0
        assert b == a
    b = [2, 1]
    assert bogosort(b, rng) >= 1
    assert b == [1, 2]


def test_is_sorted() -> None:
    for n in range(6):
        for p in itertools.permutations(range(n)):
            assert is_sorted(list(p)) == (list(p) == sorted(p))


def test_shuffle_is_uniform() -> None:
    rng = random.Random(11)
    counts: Counter[tuple[int, ...]] = Counter()
    for _ in range(12000):
        a = [0, 1, 2]
        shuffle(a, rng)
        counts[tuple(a)] += 1
    assert len(counts) == 6
    assert all(1800 < c < 2200 for c in counts.values())


def test_mean_shuffles_is_factorial() -> None:
    rng = random.Random(5)
    total = sum(bogosort([3, 1, 2], rng) for _ in range(6000))
    assert 5.5 < total / 6000 < 6.5


def test_random_against_sorted() -> None:
    rng = random.Random(2007)
    for _ in range(500):
        a = [rng.randint(0, 3) for _ in range(rng.randint(0, 5))]
        b = list(a)
        bogosort(b, rng)
        assert b == sorted(a)

What the next level needs

the tests did not run in this build

Read the full page about Bogosort