Sorting
Bubble Sort
Repeatedly compares adjacent elements and swaps them when they are out of order, so the largest unsorted value bubbles to the end after every pass.
1Detailed explanation
Bubble sort walks through the array comparing each pair of neighbours. Whenever the left value is larger than the right value they are swapped. After the first full pass the largest value has 'bubbled' to the last position; after the second pass the second-largest is in place, and so on.
Each pass can stop one position earlier because the tail of the array is already sorted. A swapped flag lets the algorithm stop early: if a whole pass makes no swap, every pair is in order and the array is sorted.
Bubble sort is rarely used in production, but it is the clearest way to learn comparisons, swaps, loop invariants and best/worst-case analysis.
2Pseudocode
procedure bubbleSort(A)
n ← length(A)
for i ← 0 to n − 2
swapped ← false
for j ← 0 to n − 2 − i
if A[j] > A[j + 1]
swap A[j] and A[j + 1]
swapped ← true
if not swapped
break // already sorted
return A3Interactive visualization
Repeatedly compares adjacent elements and swaps them when they are out of order, so the largest unsorted value bubbles to the end after every pass.
4Implementations
Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
const arr = [5, 3, 8, 1, 2];
console.log("Sorted:", bubbleSort(arr));
5Time and space complexity
Time: In the worst case (reverse-sorted input) pass i makes n−1−i comparisons, giving (n−1)+(n−2)+…+1 = n(n−1)/2 comparisons → O(n²). With the swapped flag, an already-sorted array finishes after one pass of n−1 comparisons → O(n) best case.
Space: Sorting happens in place by swapping inside the same array. Only a few index variables (i, j, swapped) are used, so auxiliary space is O(1). The input array itself occupies O(n).
6Common interview variations
- Count the number of swaps needed (equals the number of inversions).
- Sort in descending order or by a custom key.
- Explain why bubble sort is stable and in-place.
- Cocktail shaker sort: alternate left-to-right and right-to-left passes.
- Prove the best case is O(n) only with the early-exit flag.