Bubble Sort
Watch adjacent elements get compared and swapped until the largest values bubble to the end.
SortingComparisonIn-placeStable
How it works
Bubble sort walks through the array from left to right, comparing each pair of neighbours. If the left value is bigger than the right one, they swap. By the end of the first pass the largest value has "bubbled" all the way to the last position, which is now final.
Each following pass repeats the same walk over the remaining unsorted part, which shrinks by one element every time. If a whole pass finishes without a single swap, the array is already sorted and the algorithm stops early.
Implementations
function bubbleSort(array) {
for (let i = 0; i < array.length - 1; i++) {
let swapped = false;
for (let j = 0; j < array.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
[array[j], array[j + 1]] = [array[j + 1], array[j]];
swapped = true;
}
}
if (!swapped) break;
}
return array;
}
def bubble_sort(array):
a = list(array)
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped:
break
return a
Complexity
| Case | Time | When |
|---|---|---|
| Best | O(n) | Already sorted: one pass with no swaps |
| Average | O(n²) | Random order |
| Worst | O(n²) | Sorted in reverse |
Bubble sort only ever swaps neighbours in place, so it needs O(1) extra space. Equal values never jump past each other, which makes it stable.