Bubble Sort

In case you were wondering

Photo by Thomas Peham on Unsplash

Sorting algorithms are basically just a set of instructions that take an array or list as an input and arrange the items into a particular order. They are a very popular interview question. We’re starting with Bubble sort, which is the easiest of sorting algorithms.

The idea in Bubble sort is that every pair of adjacent values is compared and the two values swap positions if the first value is higher than the second. During each iteration the largest value ‘bubbles up’ towards the end of the array.

In pseudo-code:

array = [several items]
until all items are sorted {
  for each item in array(from i = 0 until i = array.length-1){
    if (array[i] > array[i+1]){
      swap (array[i], array[i+1])
    }  
  }
}

The reason we’re looping until i = array.length-1 and not i = array.length-2 is that with length-1, once we get to the last item in the array that has i = length-1 we would get inside the if condition and the value of array[i+1] would be undefined, making our if statement return false which is absolutely fine for our purpose. If you wanted to avoid that you can just change array.length-1 to array.length-2.

Example:

We have array = [4, 2, 3, 9, 1, 7], and we will use Bubble sort to sort it in ascending order.

• We start by comparing the first pair of values, 4 and 2.
• 4 is bigger than 2, so we’ll swap the two values and then move on to compare the next pair of values, 4 and 3, and do the same. This will go on until the array is sorted:

Iteration 1: [4,2,3,9,1,7] → [2,4,3,9,1,7] → [2,3,4,9,1,7] → [2,3,4,9,1,7] → [2,3,4,1,9,7] → [2,3,4,1,7,9] → End of iteration, highest element is last

Iteration 2: [2,3,4,1,7,9] → [2,3,4,1,7,9] → [2,3,4,1,7,9] → [2,3,1,4,7,9] → [2,3,1,4,7,9] → [2,3,1,4,7,9] → End of iteration

Iteration 3: [2,3,1,4,7,9] → [2,3,1,4,7,9] → [2,1,3,4,7,9] → [2,1,3,4,7,9] → [2,1,3,4,7,9] → [2,1,3,4,7,9] → End of iteration

Iteration 4: [2,1,3,4,7,9] → [1,2,3,4,7,9] → [1,2,3,4,7,9] → [1,2,3,4,7,9] → [1,2,3,4,7,9] → [1,2,3,4,7,9] → End of iteration

Iteration 5: [1,2,3,4,7,9] → [1,2,3,4,7,9] → [1,2,3,4,7,9] → [1,2,3,4,7,9] → [1,2,3,4,7,9] → [1,2,3,4,7,9] → End of iteration

If you look at the 4th iteration you can see that after that the array is already sorted: Bubble sort though performs an extra check through the array to ensure that there are no other swaps left, before returning the array.

So with each iteration the n largest element will bubble up itself in the nth to last position.

Bubble sort

Note that at the first iteration the largest number finds itself in last position as it should. With the second iteration the second largest number would be in second-last position, and so on. So after array.length — 1 iterations we are guaranteed to have a sorted array.

In actual code:

Here’s one way to perform a Bubble sort:

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

This way the code will run until i = end, which means that it may also run on the already sorted array.

The iteration on line 3 makes the inner loop repeat itself for as many times as many items are in the array. We know that after array.length — 1 iterations we are guaranteed to have a sorted array, so in that line we are just making sure we cover the worst case scenario.

This is not a very efficient solution though, so let’s have a look at a better option.

Optimisation:

A slightly more efficient way would be to keep track of what has been swapped. We can create a variable swapped = false. During each iteration, if values are swapped we change swapped = true. By doing this and using a while loop, if in the previous iteration no swaps happened (hence swapped = false) we make sure that only 1 extra verification iteration happens.

The code then becomes:

let bubbleSort = (array) => {
    let end = array.length;
    let swapped;
    while (swapped) {
        swapped = false;
        for (let i = 0; i < end; i++) {
            if (array[i] > array[i + 1]) {
                let temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = true;
            }
        }
    };
    return array;
};

That’s all for Bubble sort!

Now enjoy a penguin playing with a bubble, happily unaware of any type of sorting algorithms, and a Bubble sort folk dance, because why not.

BBye