Bubble Sort
DSA · Sorting Algorithms
Theory
Bubble sort repeatedly walks through the list, compares neighbouring pairs and swaps them if they are in the wrong order. After each full pass the largest remaining element "bubbles" to its final position at the end. An early-exit check stops the algorithm when a pass makes no swaps, which makes it O(n) on already-sorted data. Its average and worst case are O(n²).
Why we use it
It is the easiest sorting algorithm to understand and is often used to teach how sorting and swapping work.
When to use it
Use it only for teaching or tiny lists. In real code use the built-in sort (Timsort) or merge/quick sort.
How it works
- Start: pass = 0
- For j = 0..n-pass-2: compare arr[j] and arr[j+1]
- arr[j] > arr[j+1]? Yes: Swap them. No: Leave them.
- Largest unsorted value has bubbled to the end
- Any swap in this pass? Yes: pass = pass + 1, next pass. No: Array is sorted: stop.
- Done
Syntax
repeat n-1 times:
for j in 0..n-2-pass:
if arr[j] > arr[j+1]: swap
stop early if no swaps
Time: O(n²) avg/worst, O(n) best Space: O(1) StableExample
def bubble_sort(arr):
n = len(arr)
for p in range(n - 1):
swapped = False
for j in range(n - 1 - p):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
print("After pass", p + 1, ":", arr)
if not swapped:
break
return arr
bubble_sort([64, 34, 25, 12, 22])Key points
- Swaps adjacent elements
- Largest element settles at the end each pass
- Stable and in place
- O(n²): too slow for large data