Sorting is the process of rearranging the items from lowest to greatest in an array and returning the sorted array.

Generally the sorting algorithm isn’t asked frequently in JS interviews but sorting a list is a quite common problem and it’s also fun to solve the sorting problem.

There are several sorting algorithms we can use such as bubble, insertion, selection, merge and quick, and in this article, we are going to see how the bubble sort algorithm works.

If you wanted to see how different sorting algorithms effectively sort data-sets from different starting points, check out this sorting algorithms animations.

First, let’s take a look at the built-in JS sort method.

Built-in JS sort method

JavaScript has its own built-in sort method but it doesn’t always give us the result we expect.

Let’s see how it works with strings.

const names = ['Chloe', 'Ryan', 'James', 'Emma', 'Chris', 'Alice'];
console.log(names.sort());

// ['Alice', 'Chloe', 'Chris', 'Emma', 'James', 'Ryan']

With the string, the sort method sorts the array in the ascending order by default. That’s what we expected. Now let’s try with numbers.

const numbers = [5, 10, 1, 3, 15, 5, -1, 27];
console.log(numbers.sort());

// [-1, 1, 10, 15, 27, 3, 5, 5]

You may have expected this to show [-1, 1, 3, 5, 5, 10, 15, 27], however the numbers were sorted in the alphabetical order instead.

To sort the numbers numerically, we can provide the optional compare function to the sort method. The comparator looks at pairs of values and sorts the values based on the returned (negative, zero, positive) value.

const numbers = [5, 10, 1, 3, 15, 5, -1, 27];

function compareNumbers(num1, num2) {
  return num1 - num2;
}

console.log(numbers.sort(compareNumbers));

// Or ES2015
// numbers.sort((num1, num2) => num1 - num2);

// [-1, 1, 3, 5, 5, 10, 15, 27]

For the compareNumbers, if it returns:

a negative number, num1 should come before num2
a positive number, num1 should come after num2
0, num1 and num2 are the same

This is how we can define our own sorts using the built-in JS sort method.

Now let’s see how we can do the same with the bubble sort algorithm.

Bubble Sort

The basic idea of the bubble sort algorithm is where largest values bubble up to the end of the list.

The runtime of the bubble sort is O(n^2) so it is a slow algorithm for the large data set. But if we know the dataset is always going to be small or nearly sorted, using the bubble sort is ok as the runtime will be linear. For the large data set, the merge or quick sort algorithm has better runtime.

Let’s take a look at the problem and its solution with optimisation.

Problem

Write a function that takes in an array of integers, sorts it by using the bubble sort algorithm and returns a sorted version of that array.

Input

const array = [20, 7, 6, 28, 13, 1, 13, 8] // or [3, 45, -4, 7, 17, 7, 2]

Output

[1, 6, 7, 8, 13, 13, 20, 28] // or [-4, 2, 3, 7, 7, 17, 45]

Bubble Sort walkthrough

Let’s visualise the array in a graph. In the graph, the numbers represent the values in the array and the height of the graph represents the relative height based on the value.

The bubble sort uses two loops, outer and inner loop (that’s why the time complexity is quadratic time). The outer loop will go through each index, and in each outer loop, there will be inner loops going from first to last index. Let’s start with 1st outer loop.

1st outer loop

We are going to loop the array and compare the current and next numbers.

1st inner loop

If the first number (index 0), 20, is greater than the second number (index 1), 7, we will swap them. Otherwise nothing happens and move to the next number. In our case, 20 is greater than 7 so 20 (index 0) will get swapped with 7 (index 1).

2nd inner loop

Next let’s compare 20 (index 1) and 6 (index 2). As 20 is greater than 6, they will get swapped.

3rd inner loop

Next, as 20 (index 2) is less than 28 (index3), nothing will happen and move on to next inner iteration.

4th inner loop

28 (index 3) is greater than 13 (index 4), they will get swapped.

And continue on, it will compare till the end of the array (index 7) and the final result of the 1st outer loop will look something like the screenshot below.

After 1st outer loop, 28 which is the greatest number in the given array, will moved to the last index.

2nd outer loop

Let’s go through the 2nd outer loop.

1st inner loop

7 is greater than 6, so they will be swapped.

2nd inner loop

7 is less than 20, nothing will happen.

As you can guess where we are getting it, let’s fast-forward to the right before the last index and it will look like below.

Now because we have already sorted the last index (28) from the 1st outer loop, we don’t have to compare it in the last inner loop.

And after 2nd outer loop, the array will look like below.

Let’s fast-forward to the 5th outer loop. So after 4th outer loop, the numbers will get sorted as the below screenshot.

5th outer loop

Let’s start with the 1st inner loop.

1st inner loop

As 6 is greater than 1, they will get swapped.

2nd inner loop till the end

Nothing will change till the number 8 (index 3) and the result of the 5th outer loop will look like this:

6th outer loop

As you can see, they are already sorted, however the algorithm won’t actually know it. So even if it is sorted early, the algorithm will keep running to the end.

To improve it, we are going to apply the optimisation. I will talk in the following section but basically we are going to check if it’s already sorted or not and if it’s sorted, we will break out of the loop without running to the end.

In our case, once the 6th outer loop is finished, we know no swap happened so we will break out of the loop without going through the further outer loops.

This is how the bubble sort works. With this details, let’s write the code.

Solution

Here is the completed code with the optimisation.

function bubbleSort(array) {
  let isSwapped = false;
        
  for(let i = array.length; i > 0; i--) {
    isSwapped = false;
    for(let j = 0; j < i - 1; j++) {
      if (array[j] > array[j+1]) {
        swap(j, array);
        isSwapped = true;
      }
    }
                
    if (!isSwapped) break;
  }
        
  return array;
}

function swap(j, array) {
  const temp = array[j];
                  
  array[j] = array[j+1];
  array[j+1] = temp;
}

Let’s start with this function below and write the code line by line.

function bubbleSort(array) {
 
  return array;
}

We are going to receive an array and return the sorted array.

As we saw in the walkthrough above, we are going to have the outer loop and inner loop. We are going to use for loop rather than for of because it’s easier to access the index of array.

function bubbleSort(array) {
  for(let i = array.length; i > 0; i--) {
    for(let j = 0; j < i - 1; j++) {

    }
  }

  return array;
}

So we are going through each index in the array. As we are getting const array = [20, 7, 6, 28, 13, 1, 13, 8], the array.length will be 8. So the outer loop will iterate 8 times and provide the last index number to the inner loop. For example, for the 1st outer loop, it will give 8 as the last index number subtracted by 1 in the inner loop, j < i - 1. In this way, the inner loop will start from the index 0 until the last index which is the i from the outer loop but given -1, we can get the correct last index number.

So in the 1st outer loop, we will go through from the index 0 till index 7 for the inner loop. The 2nd outer loop will go through from index 0 to index 6 and 3rd outer loop from index 0 to index 5 etc.

For the 1st inner loop, we are going to check the index 0 (current) and index 1 (next).

function bubbleSort(array) {
  for(let i = array.length; i > 0; i--) {
    for(let j = 0; j < i - 1; j++) {
      if (array[j] > array[j+1]) {

      }
    }
  }

  return array;
}

If the current index (index 0) is bigger than the next index (index 1), we will swap the number in the array. Otherwise, we will skip to the next index.

Let’s write the code for the swapping.

function bubbleSort(array) {
  for(let i = array.length; i > 0; i--) {
    for(let j = 0; j < i - 1; j++) {
      if (array[j] > array[j+1]) {
        const temp = array[j];
                  
        array[j] = array[j+1];
        array[j+1] = temp;
      }
    }
  }

  return array;
}

First, we will store the value of the current index (index 0) in a temp variable so that we can use the current value after swapping.

Now let’s swap. We will replace the current value (index 0) with the next value (index 1), and then we will assign the temp value (index 0) to the next index (index 1).

Let’s see the given array for the problem again:

const array = [20, 7, 6, 28, 13, 1, 13, 8]

As 20 is bigger than 7, after the 1st inner loop, 20 and 7 will be swapped. It will happen the same way till the end of the array and once the 1st outer loop is finished, the array will be sorted to [7, 6, 20, 13, 1, 13, 8, 28] as we saw from the walkthrough.

We can create a swap function to make this code more functional and readable.

function bubbleSort(array) {
  for(let i = array.length; i > 0; i--) {
    for(let j = 0; j < i - 1; j++) {
      if (array[j] > array[j+1]) {
        swap(j, array);
      }
    }
  }

  return array;
}

function swap(j, array) {
  const temp = array[j];
                  
  array[j] = array[j+1];
  array[j+1] = temp;
}

To make the swap function even simpler with the destructuring assignment, we could go with:

function swap(j, array) {
  [array[j], array[j+1]] = [array[j+1], array[j]];
}

As we saw from the walkthrough above, this bubble sort algorithm will go through till the end of the array. So let’s add the optimisation.

Optimisation

Let’s see the code with the optimisation in highlight first.

function bubbleSort(array) {
  let isSwapped = false;
        
  for(let i = array.length; i > 0; i--) {
    isSwapped = false;

    for(let j = 0; j < i - 1; j++) {
      if (array[j] > array[j+1]) {
        swap(j, array);
        isSwapped = true;
      }
    }
                
    if (!isSwapped) break;
  }
        
  return array;
}

function swap(j, array) {
  const temp = array[j];
                  
  array[j] = array[j+1];
  array[j+1] = temp;
}

As explained in the 6th outer loop of the walkthrough above, we are going to update the isSwapped flag when it’s swapped (line 10) then we will break out of the outer loop if no swap happened and isSwapped is false (line 14).

To do that, we are going to define isSwapped first (line 2) and each outer loop, we are going to set the isSwapped false. And in each inner loop, if we swapped (line 8), we will update isSwapped to true and we will keep going with the outer loop and repeat.

If there is no swap happened meaning isSwapped will be false (line 14), we will break out of the loop.

Big O

In general, the time complexity of bubble sort is O(n^2) - quadratic time. It’s because we have a nested loop and compare each item to every single other item in the array.

If the data is nearly (or already) sorted, and with the optimisation, it’s going to be O(n) - liner time. However, we should not choose the bubble sort algorithm unless we are sure the data set is always going to be small or nearly sorted.

The space complexity is O(1) as it only requires a temp variable.