DSA Bubble Sort

How Bubble Sort Works

Bubble sort repeatedly steps through a list, compares each pair of neighboring elements, and swaps them if they are in the wrong order. After a full pass from left to right, the largest unsorted value has bubbled up into its correct final position at the end of the list, much like a bubble rising to the surface of water - hence the name.

• Compare each pair of adjacent elements from left to right
• Swap them if the left element is greater than the right element
• After one full pass, the largest remaining unsorted element is in its final position
• Shrink the unsorted portion by one and repeat the pass
• Stop early if a full pass makes zero swaps - the list is already sorted

Basic Implementation

def bubble_sort(numbers):
    n = len(numbers)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
    return numbers

print(bubble_sort([5, 2, 4, 1, 3]))  # [1, 2, 3, 4, 5]

Trace bubble_sort on [5, 2, 4, 1, 3]. Pass 1 (i=0) compares index pairs (0,1), (1,2), (2,3), (3,4) and swaps at every single one: 5 and 2 swap to give [2, 5, 4, 1, 3], then 5 and 4 swap to give [2, 4, 5, 1, 3], then 5 and 1 swap to give [2, 4, 1, 5, 3], then 5 and 3 swap to give [2, 4, 1, 3, 5] - the largest value, 5, has bubbled all the way to the last position. Pass 2 (i=1) only checks indices 0-3: 2 and 4 stay put, but 4 and 1 swap to give [2, 1, 4, 3, 5], then 4 and 3 swap to give [2, 1, 3, 4, 5]. Pass 3 (i=2) swaps 2 and 1 to give [1, 2, 3, 4, 5], and pass 4 (i=3) finds everything already in order. The final result is [1, 2, 3, 4, 5], reached after 7 total swaps across the four passes.

To avoid wasted passes once the list is already sorted, track a swapped flag during each pass: if a full pass makes zero swaps, the list must already be in order and the algorithm can stop early instead of always running all n-1 passes regardless of the data.

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

print(bubble_sort_optimized([1, 2, 3, 4, 5]))  # already sorted, exits after pass 1
print(bubble_sort_optimized([5, 2, 4, 1, 3]))  # [1, 2, 3, 4, 5]

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

print(bubble_sort_with_stats([5, 2, 4, 1, 3]))
# ([1, 2, 3, 4, 5], 10, 7)