Bubble sort repeatedly steps through the list, swapping adjacent out-of-order pairs until a pass makes no swaps. It is the canonical "first sort you learn" — easy to understand, almost never the right choice in production.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n) |
Θ(n²) |
O(n²) |
O(1) |
On each pass, compare every adjacent pair (i, i+1) and swap if out of order. The largest element "bubbles" to the end on the first pass, the second-largest on the second pass, etc. With an early-exit flag, a pass that swaps nothing means the array is sorted — that gives the O(n) best case on already-sorted input.
def bubble_sort(arr):
"""In-place bubble sort with early-exit optimization."""
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
print(bubble_sort([3, 6, 1, 8, 2, 9, 4])) # [1, 2, 3, 4, 6, 8, 9]