Loading...
Bubble Sort steps through the list, compares each pair of adjacent items, and swaps them if they are in the wrong order. After each full pass the largest remaining value "bubbles" to the end. Simple to understand but O(n²), so it is used for teaching rather than production.
Repeatedly swaps adjacent out-of-order elements until the list is sorted.
| Best case | O(n) |
| Average case | O(n²) |
| Worst case | O(n²) |
| Space | O(1) |
| Stable | Yes |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
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: # already sorted — early exit
break
return arrSorting [5, 1, 4, 2] step by step:
The control flow of the algorithm as a diagram: