Suggest an edit

Improve this article

Refine the answer for “What is the complexity of bubble sort?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

Bubble sort has the following time complexity: O(n) in the best case (with an early-exit optimization), and O(n^2) in the average and worst cases. Its space complexity is O(1); the algorithm is stable and sorts in place.

## Detailed breakdown

### Time complexity

- Best case: O(n), if a "were there any swaps" flag is used and the array is already sorted (the algorithm finishes after a single pass).
- Average case: O(n^2) - arbitrary data requires roughly n·(n-1)/2 comparisons.
- Worst case: O(n^2) - for a fully reverse-sorted array, the number of comparisons and swaps is maximal.

### Space complexity

O(1) - the sort runs in place and needs only a constant amount of extra memory (loop variables and the swap flag).

### Stability and adaptivity

- Stable: equal elements keep their relative order.
- Adaptive (with the optimization): if the array is nearly sorted, it finishes faster, down to O(n).

### Number of comparisons and swaps

- Comparisons in the worst (and average) case: n·(n-1)/2.
- Swaps in the worst case: n·(n-1)/2; in the best case - 0 (if the early exit is used).
- Without the early-exit flag, even a sorted array will still run ~n·(n-1)/2 comparisons.

### Optimizations

- The swapped flag: if no swaps happened during a pass - the array is sorted, so exit (gives the O(n) best case).
- Shrinking the bound: after each pass the last element is in its final place - shrink the inner loop's length.
- Remembering the last swap position: lets you shrink the next pass's range even further.
- Bidirectional (cocktail) bubble sort: pushes large elements right and small ones left in a single cycle, speeding things up on some data.

### When to use it, and when not to

- Use it: for teaching purposes, very small arrays, nearly sorted data, when implementation simplicity and stability matter.
- Don't use it: for medium and large arrays in production - there are O(n log n) algorithms that run faster (quicksort, mergesort, heapsort).

### Example: optimized bubble sort (JavaScript, ES6)

```
function bubbleSort(arr) {
  const a = arr.slice(); // do not mutate the original array
  let n = a.length;
  let swapped;
  do {
    swapped = false;
    for (let i = 1; i < n; i++) {
      if (a[i - 1] > a[i]) {
        [a[i - 1], a[i]] = [a[i], a[i - 1]]; // swap
        swapped = true;
      }
    }
    n--; // the last element is already in place
  } while (swapped);
  return a;
}

console.log(bubbleSort([5, 1, 4, 2, 8])); // [1, 2, 4, 5, 8]
```

### Example: bidirectional (cocktail) bubble sort

```
function cocktailSort(arr) {
  const a = arr.slice();
  let left = 0;
  let right = a.length - 1;
  let swapped = true;

while (swapped) {
    swapped = false;
    // left-to-right pass
    for (let i = left; i < right; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    right--;
    if (!swapped) break;

swapped = false;
    // right-to-left pass
    for (let i = right; i > left; i--) {
      if (a[i - 1] > a[i]) {
        [a[i - 1], a[i]] = [a[i], a[i - 1]];
        swapped = true;
      }
    }
    left++;
  }
  return a;
}

console.log(cocktailSort([3, 0, 2, 5, -1, 4, 1])); // [-1, 0, 1, 2, 3, 4, 5]
```

### Comparison with other algorithms

- Insertion sort: also O(n^2), but usually faster than bubble sort in practice; best case O(n) with no extra memory, stable.
- Selection sort: O(n^2), a minimal number of swaps (O(n)), but unstable; often faster than bubble sort in terms of memory writes.
- Quicksort / Mergesort / Heapsort: asymptotically faster for large n - O(n log n), the preferred choice for production.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts629 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.