Easy difficulty · Algorithm · Topics: sorting, comparison-sort, stable
Bubble sort orders an array by repeatedly comparing neighbouring elements and swapping them when they are in the wrong order. After each pass over the array, the largest remaining value has "bubbled up" to its final position at the right end. This version stops early when a whole pass makes no swap.
Imagine bubbles rising in a glass of soda: big bubbles rise past small ones. Here the big numbers rise to the right. Each comparison only fixes one pair, but a large value keeps being swapped forward until it meets something larger, so one pass is enough to put the maximum of the unsorted part at the end.
The invariant: after pass p, the last p + 1 elements are in their final sorted positions. That is why the inner loop can shrink by one each pass. If a pass swaps nothing, every neighbouring pair is already in order, so the array is sorted and we can stop.
pass = 0 .. n - 2.swapped = false.j = 0 .. n - 2 - pass, compare nums[j] and nums[j + 1].nums[j] > nums[j + 1], swap them and set swapped = true.swapped is still false, break: the array is sorted.Test case 0: nums = [5, 2, 9, 1, 7, 3].
| Pass | Swaps made | Array after the pass | Note |
|---|---|---|---|
| 0 | 4 | [2, 5, 1, 7, 3, 9] | 9 bubbled to the end |
| 1 | 2 | [2, 1, 5, 3, 7, 9] | 7 is now in place |
| 2 | 2 | [1, 2, 3, 5, 7, 9] | already sorted, but a swap happened |
| 3 | 0 | [1, 2, 3, 5, 7, 9] | swapped is false, so we break |
Pass 3 is the early exit: one extra pass with no swaps proves the array is sorted, so the loop never starts a fifth pass.
| Case | Time | Why |
|---|---|---|
| Best | O(n) | already sorted: one pass, no swaps, early exit |
| Average | O(n^2) | about n^2 / 4 swaps and n^2 / 2 comparisons |
| Worst | O(n^2) | reverse order needs a swap for every pair |
| Space | O(1) | sorts in place with one temporary variable |
swapped flag it is fast on nearly sorted data, but insertion sort does the same job with fewer writes.n - 1 reads nums[n], which is undefined, so comparisons go wrong.swapped flag keeps the worst-case behaviour even for sorted input.>= instead of > swaps equal elements and makes the sort unstable.swapped outside the outer loop makes the early exit never trigger (or trigger too soon).j sweeps left to right; the two bars at j and j + 1 are the pair being compared.swapped turns true.swapped staying false, then the loop breaks.Input: nums = [5, 2, 9, 1, 7, 3]
Output: [1, 2, 3, 5, 7, 9]
class Solution {
bubbleSort(nums) {
const n = nums.length;
for (let pass = 0; pass < n - 1; pass++) {
let swapped = false;
// After each pass the largest unsorted value has "bubbled" to the end,
// so the inner loop can stop one position earlier every time.
for (let j = 0; j < n - 1 - pass; j++) {
if (nums[j] > nums[j + 1]) {
const temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break; // no swaps means the array is already sorted
}
}
return nums;
}
}