Sorting

What you'll learn

How bubble sort works, why it is O(n squared), and what faster sorts do differently.

Why it matters

Sorted data is much easier to search, compare and display. Sorting is also one of the best places to learn how to reason about algorithms.

Explanation

Bubble sort repeatedly walks through the list and swaps neighbours that are in the wrong order. After each full pass, the biggest unsorted value has "bubbled" to the right end.

It is simple but slow: up to n passes over n items is O(n squared).

Faster sorts, such as merge sort and quick sort, use a divide-and-conquer approach and reach O(n log n). That is what Array.prototype.sort uses in practice.

Example

Step-by-step walkthrough

5

2

9

1

6

Start: we will bubble the biggest value to the right, one pass at a time.

Play

1. Compare 5 and 2. Out of order, so swap.
2. Compare 5 and 9. Fine, no swap. Compare 9 and 1: swap. Compare 9 and 6: swap.
3. The first pass ends with 9 in its final place at the right edge.
4. Passes repeat over the shorter unsorted part until a pass makes no swaps.
5. The code prints [ 1, 2, 5, 6, 9 ].

Try insertion sort too, which builds the sorted group one item at a time:

5

2

9

1

6

Start: the first value is a sorted group of one.

Play

Try it yourself

Add a counter for how many swaps happen, and compare a sorted input with a reversed one.

Count swapsJavaScript

Editable codefunction bubbleSort(arr) { const a = [...arr]; let swaps = 0; for (let end = a.length - 1; end > 0; end--) { for (let j = 0; j < end; j++) { if (a[j] > a[j + 1]) { [a[j], a[j + 1]] = [a[j + 1], a[j]]; swaps++; } } } return { sorted: a, swaps }; } console.log(bubbleSort([1, 2, 3, 4, 5])); console.log(bubbleSort([5, 4, 3, 2, 1]));

Run ResetCopyCtrl+Enter to run

Common mistakes

• Sorting numbers with default sort() in JavaScript: it compares as text. Use arr.sort((a, b) => a - b).
• Mutating the input when you meant to return a copy.
• Reading past the end with a[j + 1].
• Using bubble sort on big inputs. Prefer the built-in sort.

Quick quiz

Summary

• Bubble sort swaps neighbours until nothing is out of order. It is O(n squared).
• Faster sorts are O(n log n).
• Always give sort a compare function for numbers.

Next: binary search, which needs sorted data.

function bubbleSort(arr) {
  const a = [...arr];
  for (let end = a.length - 1; end > 0; end--) {
    for (let j = 0; j < end; j++) {
      if (a[j] > a[j + 1]) {
        const tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
      }
    }
  }
  return a;
}

console.log(bubbleSort([5, 2, 9, 1, 6]));