Bubble sort in Python
Repeatedly swaps adjacent out-of-order pairs, so large elements bubble to the end; quadratic and rarely preferred.
- File
bubble_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/bubble-sort/. The authors are listed in prov/JS56R4.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def bubble_sort(a: list[T]) -> int:
"""Sort a in place, in non-decreasing order, and return the number of passes.
Each pass exchanges adjacent items that are out of order. The next pass
stops at the place of the last exchange. The sort is stable.
Cost: Theta(n + d) exchanges and O(n^2) comparisons, d = inversions.
"""
passes = 0
bound = len(a) - 1 # @line L1
while bound > 0: # @line L2
passes += 1
last = 0 # @line L3
for j in range(bound): # @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 # @line L7
bound = last # @line L8
return passes
test_bubble_sort.py 57 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bubble-sort/. The authors are listed in prov/JS56R4.jsonl.
import itertools
import random
from bubble_sort import bubble_sort
def test_example() -> None:
a = [5, 1, 4, 2, 8, 0, 3]
assert bubble_sort(a) == 5
assert a == [0, 1, 2, 3, 4, 5, 8]
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)
bubble_sort(b)
assert b == sorted(a)
def test_sorted_input_takes_one_pass() -> None:
a = list(range(20))
assert bubble_sort(a) == 1
def test_passes_bound() -> None:
for n in range(1, 7):
for p in itertools.permutations(range(n)):
m = max([sum(1 for i in range(p.index(v)) if p[i] > v) for v in p])
b = list(p)
passes = bubble_sort(b)
assert b == list(range(n))
assert m <= passes <= m + 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")]
bubble_sort(a)
assert [x.tag for x in a] == ["b", "d", "a", "c"]
def test_random_against_sorted() -> None:
rng = random.Random(1956)
for _ in range(600):
a = [rng.randint(-30, 30) for _ in range(rng.randint(0, 50))]
b = list(a)
bubble_sort(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build