Bubble sort

Easy TimeO(n²) SpaceO(1)

Given an array arr of numbers, sort it into ascending order in place, exchanging only values that sit next to each other. Equal neighbours are never exchanged, which is what keeps the sort stable.

Examples

Example 1

Input
arr = [5, 2, 8, 1, 4]
Output
[1,2,4,5,8]
The same five values, ascending.

Example 2

Input
arr = [1, 2, 3]
Output
[1,2,3]
Already in order: 3 comparisons and not one exchange.

The Code

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        const tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
  return arr;
}
bubbleSort([5, 2, 8, 1, 4]);
Done

The first 18 calls, of 20. This one does not fit on a page.

Step through bubbleSort([5, 2, 8, 1, 4]) call by call

More like this

All sorting examples (8) →