sorts.bubble_sort

Attributes

T
num_runs

Classes

Comparable

Base class for protocol classes.

Functions

bubble_sort_iterative(→ list[T])	Pure implementation of the bubble sort algorithm in Python (iterative).
bubble_sort_recursive(→ list[T])	Pure implementation of the bubble sort algorithm in Python (recursive).

Module Contents

class sorts.bubble_sort.Comparable

Bases: Protocol

Base class for protocol classes.

Protocol classes are defined as:

class Proto(Protocol):
    def meth(self) -> int:
        ...

Such classes are primarily used with static type checkers that recognize structural subtyping (static duck-typing).

For example:

class C:
    def meth(self) -> int:
        return 0

def func(x: Proto) -> int:
    return x.meth()

func(C())  # Passes static type check

See PEP 544 for details. Protocol classes decorated with @typing.runtime_checkable act as simple-minded runtime protocols that check only the presence of given attributes, ignoring their type signatures. Protocol classes can be generic, they are defined as:

class GenProto[T](Protocol):
    def meth(self) -> T:
        ...

__lt__(other: Any, /) → bool

sorts.bubble_sort.bubble_sort_iterative[T: Comparable](collection: list[T]) → list[T]

Pure implementation of the bubble sort algorithm in Python (iterative).

Bubble sort works by repeatedly stepping through the collection, comparing each pair of adjacent elements and swapping them if they are in the wrong order. This process repeats, with each full pass “bubbling” the next-largest unsorted element into its correct position at the end of the collection, until a full pass completes with no swaps, at which point the collection is sorted.

Time complexity: O(n) best case (already sorted, thanks to the early-exit optimization), O(n^2) average and worst case. Space complexity: O(1) auxiliary (sorts in place).

Parameters:

collection – some mutable ordered collection with heterogeneous

comparable items inside :return: the same collection ordered in ascending order

Examples: >>> bubble_sort_iterative([0, 5, 2, 3, 2]) [0, 2, 2, 3, 5] >>> bubble_sort_iterative([]) [] >>> bubble_sort_iterative([-2, -45, -5]) [-45, -5, -2] >>> bubble_sort_iterative([-23, 0, 6, -4, 34]) [-23, -4, 0, 6, 34] >>> bubble_sort_iterative([1, 2, 3, 4]) [1, 2, 3, 4] >>> bubble_sort_iterative([3, 3, 3, 3]) [3, 3, 3, 3] >>> bubble_sort_iterative([56]) [56] >>> bubble_sort_iterative([0, 5, 2, 3, 2]) == sorted([0, 5, 2, 3, 2]) True >>> bubble_sort_iterative([]) == sorted([]) True >>> bubble_sort_iterative([-2, -45, -5]) == sorted([-2, -45, -5]) True >>> bubble_sort_iterative([-23, 0, 6, -4, 34]) == sorted([-23, 0, 6, -4, 34]) True >>> bubble_sort_iterative([‘d’, ‘a’, ‘b’, ‘e’]) == sorted([‘d’, ‘a’, ‘b’, ‘e’]) True >>> bubble_sort_iterative([‘z’, ‘a’, ‘y’, ‘b’, ‘x’, ‘c’]) [‘a’, ‘b’, ‘c’, ‘x’, ‘y’, ‘z’] >>> bubble_sort_iterative([1.1, 3.3, 5.5, 7.7, 2.2, 4.4, 6.6]) [1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7] >>> bubble_sort_iterative([1, 3.3, 5, 7.7, 2, 4.4, 6]) [1, 2, 3.3, 4.4, 5, 6, 7.7] >>> import random >>> collection_arg = random.sample(range(-50, 50), 100) >>> bubble_sort_iterative(collection_arg) == sorted(collection_arg) True >>> import string >>> collection_arg = random.choices(string.ascii_letters + string.digits, k=100) >>> bubble_sort_iterative(collection_arg) == sorted(collection_arg) True >>> bubble_sort_iterative([1, “a”]) # doctest: +IGNORE_EXCEPTION_DETAIL Traceback (most recent call last):

…

TypeError: ‘<’ not supported between instances of ‘str’ and ‘int’

sorts.bubble_sort.bubble_sort_recursive[T: Comparable](collection: list[T]) → list[T]

Pure implementation of the bubble sort algorithm in Python (recursive).

Functionally identical to the iterative version: each call makes a single pass through the collection, comparing adjacent elements and swapping any pair that is out of order. If any swap occurred during the pass, the function calls itself again on the (partially sorted) collection; once a pass completes with no swaps, the collection is sorted and the recursion stops.

Time complexity: O(n) best case (already sorted), O(n^2) average and worst case. Space complexity: O(1) auxiliary for the sort itself (sorts in place), though the recursion adds O(n) call-stack frames in the worst case.

Parameters:

collection – mutable ordered sequence of elements

Returns:

the same list in ascending order

Examples: >>> bubble_sort_recursive([0, 5, 2, 3, 2]) [0, 2, 2, 3, 5] >>> bubble_sort_recursive([]) [] >>> bubble_sort_recursive([-2, -45, -5]) [-45, -5, -2] >>> bubble_sort_recursive([-23, 0, 6, -4, 34]) [-23, -4, 0, 6, 34] >>> bubble_sort_recursive([0, 5, 2, 3, 2]) == sorted([0, 5, 2, 3, 2]) True >>> bubble_sort_recursive([]) == sorted([]) True >>> bubble_sort_recursive([-2, -45, -5]) == sorted([-2, -45, -5]) True >>> bubble_sort_recursive([-23, 0, 6, -4, 34]) == sorted([-23, 0, 6, -4, 34]) True >>> bubble_sort_recursive([‘d’, ‘a’, ‘b’, ‘e’]) == sorted([‘d’, ‘a’, ‘b’, ‘e’]) True >>> bubble_sort_recursive([‘z’, ‘a’, ‘y’, ‘b’, ‘x’, ‘c’]) [‘a’, ‘b’, ‘c’, ‘x’, ‘y’, ‘z’] >>> bubble_sort_recursive([1.1, 3.3, 5.5, 7.7, 2.2, 4.4, 6.6]) [1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7] >>> bubble_sort_recursive([1, 3.3, 5, 7.7, 2, 4.4, 6]) [1, 2, 3.3, 4.4, 5, 6, 7.7] >>> bubble_sort_recursive([‘a’, ‘Z’, ‘B’, ‘C’, ‘A’, ‘c’]) [‘A’, ‘B’, ‘C’, ‘Z’, ‘a’, ‘c’] >>> import random >>> collection_arg = random.sample(range(-50, 50), 100) >>> bubble_sort_recursive(collection_arg) == sorted(collection_arg) True >>> import string >>> collection_arg = random.choices(string.ascii_letters + string.digits, k=100) >>> bubble_sort_recursive(collection_arg) == sorted(collection_arg) True >>> bubble_sort_recursive([1, “a”]) # doctest: +IGNORE_EXCEPTION_DETAIL Traceback (most recent call last):

…

TypeError: ‘<’ not supported between instances of ‘str’ and ‘int’

sorts.bubble_sort.T

sorts.bubble_sort.num_runs = 10000