~/blog

Bubble Sort

Jun 2, 2026•8 min read•By Mohammed Vasim

dsapythondata-structuresalgorithmsproblem-solving

A Concrete Walkthrough

Tracing [9, 3, 7, 1, 6, 2].

Bubble sort scans left to right, swapping adjacent elements that are out of order. After each full scan (a pass), the largest unsorted element reaches its final position at the right end.

Pass 1

j	Pair (arr[j], arr[j+1])	Out of order?	Swap?	Array after
0	(9, 3)	9 > 3? Yes	Swap	[3, 9, 7, 1, 6, 2]
1	(9, 7)	9 > 7? Yes	Swap	[3, 7, 9, 1, 6, 2]
2	(9, 1)	9 > 1? Yes	Swap	[3, 7, 1, 9, 6, 2]
3	(9, 6)	9 > 6? Yes	Swap	[3, 7, 1, 6, 9, 2]
4	(9, 2)	9 > 2? Yes	Swap	[3, 7, 1, 6, 2, 9]

After pass 1, the largest element (9) is at index 5 — its final position. Every remaining pass can ignore the last element.

Pass 2

Scan indices 0–3 (index 4 is where 9 settled).

j	Pair	Out of order?	Swap?	Array after
0	(3, 7)	No	—	[3, 7, 1, 6, 2, 9]
1	(7, 1)	7 > 1? Yes	Swap	[3, 1, 7, 6, 2, 9]
2	(7, 6)	7 > 6? Yes	Swap	[3, 1, 6, 7, 2, 9]
3	(7, 2)	7 > 2? Yes	Swap	[3, 1, 6, 2, 7, 9]

Second largest (7) reaches index 4.

Pass 3

Scan indices 0–2.

j	Pair	Out of order?	Swap?	Array after
0	(3, 1)	3 > 1? Yes	Swap	[1, 3, 6, 2, 7, 9]
1	(3, 6)	No	—	[1, 3, 6, 2, 7, 9]
2	(6, 2)	6 > 2? Yes	Swap	[1, 3, 2, 6, 7, 9]

Pass 4

Scan indices 0–1.

j	Pair	Out of order?	Swap?	Array after
0	(1, 3)	No	—	[1, 3, 2, 6, 7, 9]
1	(3, 2)	3 > 2? Yes	Swap	[1, 2, 3, 6, 7, 9]

Pass 5

Scan index 0.

j	Pair	Out of order?	Swap?	Array after
0	(1, 2)	No	—	[1, 2, 3, 6, 7, 9]

Zero swaps. The algorithm detects this and exits early. Pass 6 is never executed.

Given an unsorted array, rearrange it in ascending order by repeatedly comparing adjacent elements and swapping them if they are out of order. Each pass places the next largest element in its final position, and the array is sorted when a pass completes with zero swaps.

Code

python

def bubble_sort(arr):
    n = len(arr)

    for i in range(n - 1):
        swapped = False

        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        if not swapped:
            break

    return arr

Line by line:

for i in range(n - 1): — outer loop for passes. At most n - 1 passes guarantee the array is sorted.
swapped = False — flag reset each pass. Tracks whether any swap occurred.
for j in range(n - 1 - i): — inner loop compares adjacent pairs. The range shrinks by i because the last i elements are already in their final positions.
if arr[j] > arr[j + 1]: — out of order? Swap. Strict > (not >=) makes the sort stable.
swapped = True — a swap occurred this pass.
if not swapped: break — early exit. If a full pass has zero swaps, the array is sorted.

Edge case — single element. range(0) for outer loop. Zero passes. Returns immediately.

Edge case — already sorted. Pass 1 scans once, makes zero swaps, exits. O(n) best case.

Time: O(n²) average and worst. O(n) best (early exit). Space: O(1).

Code Trace

Tracing bubble_sort([9, 3, 7, 1, 6, 2]):

Pass i	j range	Comparisons	Swaps this pass	swapped?	Array after pass
0	0–4	(9,3)✓, (9,7)✓, (9,1)✓, (9,6)✓, (9,2)✓	5	True	[3, 7, 1, 6, 2, 9]
1	0–3	(3,7)✗, (7,1)✓, (7,6)✓, (7,2)✓	3	True	[3, 1, 6, 2, 7, 9]
2	0–2	(3,1)✓, (3,6)✗, (6,2)✓	2	True	[1, 3, 2, 6, 7, 9]
3	0–1	(1,3)✗, (3,2)✓	1	True	[1, 2, 3, 6, 7, 9]
4	0	(1,2)✗	0	False	break

5 passes instead of 6. Total comparisons: 5 + 4 + 3 + 2 + 1 = 15. The early exit at pass 4 saved one full scan.

Bubble sort is the most intuitive sort to visualise but the least practical. Every swap is explicit, every pass makes the next largest element surface to its correct position. That transparency makes it the right tool for teaching — and the wrong tool for production. Python's list.sort() uses Timsort, a hybrid that runs in O(n log n) and exploits existing order.

→ LeetCode 912: Sort an Array — bubble sort will time out on the large test cases.