sorts.bubble_sort

Attributes

num_runs

Functions

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

Module Contents

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

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

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

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

sorts.bubble_sort.num_runs = 10000