Bubble Sort and Cocktail Shaker Sort in JavaScript

Introduction

Bubble Sort, sometimes also referred to as Sinking Sort is one of the most widely known sorting algorithms. It is usually one of the first sorting algorithms that CS students come across due to its simplicity and the fact that it is quite intuitive and easy to translate into code.

However, this simple algorithm has shown poor performance in real-life problems. Especially compared to faster, more popular and widely used algorithms like Quicksort or Merge Sort. This is why Bubble Sort is used primarily as an educational tool.

In this article, we'll explain how Bubble Sort works and implement it in JavaScript. We will also check out its time complexity, and compare it to some other sorting algorithms.

Additionally, we'll implement one of its variants - Cocktail Shaker Sort in an attempt to optimize it.

Bubble Sort

Bubble Sort is a comparison-type sorting algorithm. This means that it compares individual elements within the collection during runtime. Depending on your data type and purpose, the comparison can be done via a relational operator or through a custom comparison function.

The idea behind Bubble Sort is rather simple. Starting from the beginning of the collection we want to be sorted - we compare elements within a pair. If the pair is in the desired order, we do nothing. If it isn't, we swap the elements it consists of.

This is done again, and again, until all elements in the collection are sorted. Let's look at a visual representation of how Bubble Sort works:

Taking a look at the element with the value of 8, we can see it "bubbling up" from the beginning of the array to its proper place. This is where the name of "Bubble Sort" comes from.

Bubble Sort Implementation

Now that we've went over the idea behind Bubble Sort, we can start with the implementation:

function bubbleSort(inputArr) {
    let n = inputArr.length;
    
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            // Comparing and swapping the elements
            if(inputArr[j] > inputArr[j+1]){
                let t = inputArr[j];
                inputArr[j] = inputArr[j+1];
                inputArr[j+1] = t;
            }
        }
    }
    return inputArr;
}

The implementation is pretty intuitive. We iterate through the array n times with a for loop, where n is the length of the array. For each iteration, we "bubble up" an element to its correct place. This is done through another for loop that compares the element to its adjacent one, switching them if need be.

Finally, we return the sorted array. Let's populate an array and sort it:

let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);

Running this code will yield:

(5) [1, 2, 4, 5, 8]

Let's take a look at how this is done with concrete values:

First iteration:

[5, 1, 4, 2, 8] -> [1, 5, 4, 2, 8] - We are swapping 5 and 1, since 5 > 1
[1, 5, 4, 2, 8] -> [1, 4, 5, 2, 8] - We are swapping 5 and 4, since 5 > 4
[1, 4, 5, 2, 8] -> [1, 4, 2, 5, 8] - We are swapping 5 and 2, since 5 > 2
[1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] - No change, since 5 < 8

Second iteration:

[1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] - No change, since 1 < 4
[1, 4, 2, 5, 8] -> [1, 2, 4, 5, 8] - We are swapping 4 and 2, since 4 > 2
[1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] - No change, since 4 < 5
[1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] - No change, since 5 < 8

The array is sorted within two iterations, however, our algorithm will continue running n times, comparing all the elements over and over again. This is because we've told it to iterate inputArr.length times.

Bubble Sort is inefficient in and of itself - especially with a flaw like this. There are two things we can do to optimize it, though.

Optimizations

The first optimization we can implement is - terminate the algorithm if the array is sorted - i.e. no swaps are made. This can be done via a boolean flag. Each time we swap any elements, it's set to true:

function bubbleSort(inputArr) {
    let n = inputArr.length;
    let sorted = false;
        
    while (!sorted) {
        sorted = true;
        for(let i = 0; i < n; i++){
            if(inputArr[i] > inputArr[i+1]){
                let t = inputArr[i];
                inputArr[i] = inputArr[i+1];
                inputArr[i+1] = t;
                sorted = false;
            }
        }
    }
    return inputArr;
}

As soon as we finish iterating through the array, and no swaps were made, the while loop will stop looping and the array is returned.

Let's populate the array again and sort it:

let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);

This code results in:

[1, 2, 4, 5, 8]

A thing that's worth noting is that with the first iteration finished, the largest element will be located at the end of the array. The next iteration will place the second largest element before the largest one, and so on.

This means that with each iteration, we don't really need to look at the last element, since we know it's in the right place. Thus, in the k-th iteration, we only really need to take a look at n-k+1 iterations:

function bubbleSort(inputArr) {
        
    let n = inputArr.length;
    let sorted = false;
    let numOfIterations = 0;
        
    while(!sorted) {
        sorted = true;
        for(let i = 0; i < n-numOfIterations+1; i++){
            if(inputArr[i] > inputArr[i+1]){
                let t = inputArr[i];
                inputArr[i] = inputArr[i+1];
                inputArr[i+1] = t;
                sorted = false;
                numOfIterations++;
            }
        }
    }  
    return inputArr;
}

Let's populate the array again and sort it:

let inputArr = [5,1,4,2,8];
bubbleSort(inputArr);
console.log(inputArr);

This code results in:

(5) [1, 2, 4, 5, 8]

Cocktail Shaker Sort vs Bubble Sort

Another optimization of Bubble Sort is its derived variant called Cocktail Shaker Sort, also known as Bidirectional Bubble Sort or simply Cocktail Sort.

This algorithm extends Bubble Sort by operating in two directions. Instead of going from the start to finish, and repeating that, it goes from start to finish, and then from finish to start again, in a single full iteration. Effectively, it accomplishes double the work of Bubble Sort in a single full iteration, though in practice it doesn't typically perform two times faster.

This is because it has a similar comparison-count. It compares more elements per iteration than regular Bubble Sort and it does double the swaps per iteration. The reason it's faster is because the range of possible swaps per iteration gets smaller and smaller, giving it a slightly better performance.

Let's go ahead and implement the algorithm:

function cocktailShakerSort(inputArr) {

    let n = inputArr.length;
    let sorted = false;

    while (!sorted) {
        sorted = true;
        for (let i = 0; i < n - 1; i++) {
            if (inputArr[i] > inputArr[i + 1]){
               let tmp = inputArr[i];
               inputArr[i] = inputArr[i + 1];
               inputArr[i+1] = tmp;
               sorted = false;
            }
   }

   if (sorted)
       break;
   sorted = true;

        for (let j = n - 1; j > 0; j--) {
            if (inputArr[j-1] > inputArr[j]) {
                let tmp = inputArr[j];
                inputArr[j] = inputArr[j + 1];
                inputArr[j+1] = tmp;
                sorted = false;
            }
        }
    }
    return inputArr;
}

The first part is the same as regular Bubble Sort. Though, after we pass forwards, we go backwards. First, we check if the array is sorted with the previous forward-pass. If not, we go backwards, swapping if necessary. If no swaps are made, the algorithm is terminated and the result is returned.

If we didn't check for swaps in the second pass, we'd have to pass an additional time forwards to verify if the array is sorted.

Let's take a look at the manual example from before - this time, with Cocktail Shaker:

[5, 1, 4, 2, 8] -> [1, 5, 4, 2, 8] - We are swapping 5 and 1, since 5 > 1
[1, 5, 4, 2, 8] -> [1, 4, 5, 2, 8] - We are swapping 5 and 4, since 5 > 4
[1, 4, 5, 2, 8] -> [1, 4, 2, 5, 8] - We are swapping 5 and 2, since 5 > 2
[1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] - No change, since 5 < 8
[1, 4, 2, 5, 8] -> [1, 4, 2, 5, 8] - No change, since 5 > 2
[1, 4, 2, 5, 8] -> [1, 2, 4, 5, 8] - We are swapping 4 and 2, since 2 < 4
[1, 2, 4, 5, 8] -> [1, 2, 4, 5, 8] - No change, since 2 > 1

Here, our array is sorted within 1 iteration, unlike Bubble Sort's 2 iterations. Cocktail Sort did this with 7 comparisons, whereas Bubble Sort did this with 8. This isn't a lot at this scale, though with larger numbers, we'll see performance boosts.

Typically, this results in a 33% faster performance.

Donald E. Knuth mentioned Cocktail Shaker Sort, along with a few similar Bubble Sort variants, in his famous monograph "The Art of Computer Programming":

But none of these refinements leads to an algorithm better than straight insertion [that is, insertion sort]; and we already know that straight insertion isn't suitable for large N. [...]

In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.

Time Complexity and Comparison

Since our array contains n elements, Bubble Sort performs O(n) comparisons, n times. This leads us to a total running time of O(n²) - average and worst-case. This is a horrible time complexity for a sorting algorithm.

For reference, most common sorting algorithms, such as Quicksort or Merge Sort, have an average running time of O(nlogn).

Theoretically, Bubble Sort could have a O(n) complexity, if we run it on a sorted collection, which outperforms all other algorithms except Insertion Sort and Cube Sort. Though, the rarity of this case doesn't justify using it in practice.

Using the built-in console.time() function, we can compare the time it takes to run the code on arrays of different lengths:

console.time('bubble');
bubbleSort(inputArr);
console.timeEnd('bubble');

We'll be doing this for arrays of size 100, 1 000 and 10 000:

Number of elements	Unoptimized Bubble Sort	Bubble Sort with a 'boolean' flag	Bubble Sort with n-k+1 iterations	Cocktail Shaker Sort
100	2ms	1ms	1ms	1ms
1000	8ms	6ms	1ms	1ms
10 000	402ms	383ms	2ms	1ms

What's evident here is just how inefficient the first implementation is compared to variants like Cocktail Shaker.

Conclusion

Although Bubble Sort is very intuitive and easy to understand and implement, it is highly impractical for solving most problems.

It has an average and worst-case running time of O(n²), and can only run on its best-case running time of O(n) when the array is already sorted.

Its space complexity is O(1), which is great. Unfortunately, that's not nearly enough to make up for the awful time complexity.

Even among simple O(n²) sorting algorithms, Insertion Sort or Selection Sort are usually considerably more efficient.

Due to its simplicity, Bubble Sort is often used as an introduction to sorting algorithms at introductory computer science courses.