Bubble Sort

What is Bubble Sort?

Bubble Sort is one of the simplest sorting algorithms that repeatedly steps through the list by comparing adjacent elements and swapping them if they’re in the wrong order. The process will continue until the list is sorted.

Time Complexity

If we talk about its time complexity, Bubble Sort has a worst-case and average time complexity of O(n^2), where n is the number of elements in the list.

Of course, there is a best-case time complexity of O(n) when the list is already sorted, as it only requires a single pass to confirm that no swaps are needed.

However, this is not very efficient for large datasets.

How it works?

Assuming we have an array [5, 3, 8], here’s how Bubble Sort would sort it:

Compare the first two elements (5 and 3). Since 5 > 3, we swap them. The array now looks like [3, 5, 8].
Next, we compare the second and third elements (5 and 8). Since 5 < 8, no swap is needed.
We repeat the process until we make a complete pass without any swaps, indicating that the array is sorted.

Implementation

bubble_sort.py


def bubble_sort(arr: list) -> list:
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
 
arr = [5, 3, 8, 6, 7]
print(f"Unsorted array: {arr}")
 
sorted_arr = bubble_sort(arr)
print(f"Sorted array: {sorted_arr}")

Visualization

Bubble Sort Visualization

Comparisons: 0 | Swaps: 0

Unsorted

Comparing

Swapping

Sorted

Animation Controls

Animation Speed (ms)

Algorithm Info

Bubble Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Time Complexity

Best Case: O(n)
Average Case: O(n²)
Worst Case: O(n²)

Space Complexity

O(1) - In-place sorting algorithm