Bubble Sort

Bubble Sort is a simple sorting algorithm that works by comparing adjacent elements and swapping them if they are in the wrong order. The process repeats until no more swaps occur.

Algorithm

1. Compare adjacent elements.
2. If the first is larger, swap them.
3. Repeat to the end of the array.
4. Repeat from the beginning until no swaps happen.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

Example

data = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(data))  # [11, 12, 22, 25, 34, 64, 90]

Visualization

[64, 34, 25, 12]  -> compare 64, 34 -> swap
[34, 64, 25, 12]  -> compare 64, 25 -> swap
[34, 25, 64, 12]  -> compare 64, 12 -> swap
[34, 25, 12, 64]  -> pass 1 done (64 in its correct position)

[34, 25, 12, 64]  -> pass 2
[25, 34, 12, 64]  -> swap
[25, 12, 34, 64]  -> swap

[12, 25, 34, 64]  -> pass 3, no swaps -> done

Optimization

The swapped flag allows an early stop if the array is already sorted before all passes finish.

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break  # Already sorted
    return arr

Time Complexity

Space Complexity

O(1) - in-place, no extra memory needed.

Characteristics

• Stable: Elements with equal values keep their order.
• In-place: No extra array needed.
• Adaptive: Faster when the data is nearly sorted.

When to Use It

• The data is already nearly sorted.
• The dataset is very small.
• You need simple sorting that is easy to implement.
• You need a stable sort.

Bubble Sort is slow for large data. Merge Sort is more efficient with O(n log n).