Sorting Algorithms

Bubble Sort

● Beginner ⏱ 6 min read sorting

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. After each full pass, the largest unsorted element “bubbles up” to its correct position at the end.

How It Works

Text

Array: [5, 3, 8, 1, 2]

Pass 1: compare pairs left-to-right, swap if out of order
  [5,3,8,1,2] → swap(5,3) → [3,5,8,1,2]
  [3,5,8,1,2] → 5<8, no swap
  [3,5,8,1,2] → swap(8,1) → [3,5,1,8,2]
  [3,5,1,8,2] → swap(8,2) → [3,5,1,2,8]  ← 8 is in place

Pass 2: only need to check first n-1 elements
  [3,5,1,2,8] → 3<5, no swap
  [3,5,1,2,8] → swap(5,1) → [3,1,5,2,8]
  [3,1,5,2,8] → swap(5,2) → [3,1,2,5,8]  ← 5 is in place

...and so on until fully sorted.

Naive Implementation

Python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):   # last i elements already sorted
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

nums = [5, 3, 8, 1, 2]
print(bubble_sort(nums))   # [1, 2, 3, 5, 8]

Optimised: Early Exit

If a complete pass makes no swaps, the array is already sorted. This turns the best-case complexity from O(n²) to O(n).

Python

def bubble_sort_optimised(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    # array is sorted — stop early
    return arr

# Already sorted — only 1 pass needed
print(bubble_sort_optimised([1, 2, 3, 4, 5]))   # [1, 2, 3, 4, 5]

Step-by-step Trace

Python

def bubble_sort_verbose(arr):
    n = len(arr)
    arr = 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
        print(f"Pass {i+1}: {arr}")
        if not swapped:
            break
    return arr

bubble_sort_verbose([5, 3, 8, 1, 2])
# Pass 1: [3, 5, 1, 2, 8]
# Pass 2: [3, 1, 2, 5, 8]
# Pass 3: [1, 2, 3, 5, 8]
# Pass 4: [1, 2, 3, 5, 8]  ← no swaps, exit early

Stability

Bubble sort is stable: equal elements retain their original relative order. This matters when sorting objects by one field where other fields must stay in place.

💡

Why learn bubble sort if it’s slow?

Bubble sort is rarely used in production — Python’s built-in sorted() and list.sort() use Timsort (O(n log n)). But bubble sort teaches the core concepts of comparison-based sorting and O(n²) complexity that you need before tackling merge sort and quick sort.

Complexity Table

Case	Time	Space	Note
Best case	O(n)	O(1)	Array already sorted; early exit fires after 1 pass
Average case	O(n²)	O(1)
Worst case	O(n²)	O(1)	Reverse-sorted array
Stable	Yes	—	Equal elements keep original order
In-place	Yes	—	No auxiliary array needed