Bubble Sort
M
D
r
R
A
A
R
P
from typing import Any, Protocol, TypeVar
class Comparable(Protocol):
def __lt__(self, other: Any, /) -> bool: ...
T = TypeVar("T", bound=Comparable)
def 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).
:param 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'
"""
length = len(collection)
for i in reversed(range(length)):
swapped = False
for j in range(i):
if collection[j] > collection[j + 1]:
swapped = True
collection[j], collection[j + 1] = collection[j + 1], collection[j]
if not swapped:
break # Stop iteration if the collection is sorted.
return collection
def 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.
:param collection: mutable ordered sequence of elements
:return: 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'
"""
length = len(collection)
swapped = False
for i in range(length - 1):
if collection[i] > collection[i + 1]:
collection[i], collection[i + 1] = collection[i + 1], collection[i]
swapped = True
return collection if not swapped else bubble_sort_recursive(collection)
if __name__ == "__main__":
import doctest
from random import sample
from timeit import timeit
doctest.testmod()
# Benchmark: Iterative seems slightly faster than recursive.
num_runs = 10_000
unsorted = sample(range(-50, 50), 100)
timer_iterative = timeit(
"bubble_sort_iterative(unsorted[:])", globals=globals(), number=num_runs
)
print("\nIterative bubble sort:")
print(*bubble_sort_iterative(unsorted), sep=",")
print(f"Processing time (iterative): {timer_iterative:.5f}s for {num_runs:,} runs")
unsorted = sample(range(-50, 50), 100)
timer_recursive = timeit(
"bubble_sort_recursive(unsorted[:])", globals=globals(), number=num_runs
)
print("\nRecursive bubble sort:")
print(*bubble_sort_recursive(unsorted), sep=",")
print(f"Processing time (recursive): {timer_recursive:.5f}s for {num_runs:,} runs")
About this Algorithm
Problem Statement
Given an unsorted array of n elements, write a function to sort the array
Approach
- select the first element of the array
- compare it with its next element
- if it is larger than the next element then swap them
- else do nothing
- keep doing this for every index of the array
- repeat the above process n times.
Time Complexity
O(n^2) Worst case performance
O(n) Best-case performance
O(n^2) Average performance
Space Complexity
O(1) Worst case
Founder's Name
- The term “Bubble Sort” was first used by Iverson, K in 1962.
Example
arr[] = {10, 80, 40, 30}
Indexes: 0 1 2 3
1. Index = 0, Number = 10
2. 10 < 80, do nothing and continue
3. Index = 1, Number = 80
4. 80 > 40, swap 80 and 40
5. The array now is {10, 40, 80, 30}
6. Index = 2, Number = 80
7. 80 > 30, swap 80 and 30
8. The array now is {10, 40, 30, 80}
Repeat the Above Steps again
arr[] = {10, 40, 30, 80}
Indexes: 0 1 2 3
1. Index = 0, Number = 10
2. 10 < 40, do nothing and continue
3. Index = 1, Number = 40
4. 40 > 30, swap 40 and 30
5. The array now is {10, 30, 40, 80}
6. Index = 2, Number = 40
7. 40 < 80, do nothing
8. The array now is {10, 30, 40, 80}
Repeat the Above Steps again
arr[] = {10, 30, 40, 80}
Indexes: 0 1 2 3
1. Index = 0, Number = 10
2. 10 < 30, do nothing and continue
3. Index = 1, Number = 30
4. 30 < 40, do nothing and continue
5. Index = 2, Number = 40
6. 40 < 80, do nothing
Since there are no swaps in above steps, it means the array is sorted and we can stop here.
Video Explanation
A video explaining the Bubble Sort Algorithm
Others
Bubble sort is also known as Sinking sort.
