Bubble Sort
Learn how bubble sort repeatedly swaps adjacent elements until the array is sorted.
Bubble Sort
Bubble sort repeatedly steps through the array, 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. The sorted portion grows from right to left.
How it works
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
# last i elements are already sorted
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 no swaps happened — array is already sorted
if not swapped:
break
return arrThe swapped flag is an important optimization. If a full pass completes with no swaps, the array is already sorted and there is no need to continue. This makes bubble sort O(n) on an already-sorted array.
Why it is called bubble sort
After each pass, the largest remaining element has been compared against every neighbor and swapped forward whenever needed — it "bubbles" all the way to the right. After pass 1, the largest is in place. After pass 2, the second largest is in place. And so on.
Pass 1: [5, 3, 8, 1, 9, 2]
compare 5,3 → swap [3, 5, 8, 1, 9, 2]
compare 5,8 → ok [3, 5, 8, 1, 9, 2]
compare 8,1 → swap [3, 5, 1, 8, 9, 2]
compare 8,9 → ok [3, 5, 1, 8, 9, 2]
compare 9,2 → swap [3, 5, 1, 8, 2, 9] ← 9 is now sorted
Pass 2: [3, 5, 1, 8, 2, | 9]
...8 bubbles to second-to-last positionBubble sort is one of the least efficient sorting algorithms — O(n²) in the average and worst case. It is mainly taught because the concept is easy to visualize. In practice, always use Python's built-in sorted() or .sort(), which uses Timsort — O(n log n).
Complexity
| Case | Time | Space |
|---|---|---|
| Best (already sorted) | O(n) | O(1) |
| Average | O(n²) | O(1) |
| Worst (reverse sorted) | O(n²) | O(1) |