How to implement the Bubble sort algorithm in JavaScript

In this shot, we will learn about the sorting algorithm called bubble sort and how to implement it in JavaScript.

Let’s get started.

First thing first, what is a bubble sort?

The bubble sort is a simple sorting algorithm that continues to swap adjacent values, if they are in the incorrect order, until all the values are sorted.

Simply speaking, bubble sort compares all the elements one by one and sorts them based on their values.

For example, if you are given a list of integers to sort in ascending order, we could use bubble sort and begin by comparing the first item of the list with the next one. Ff the first item is greater than the second one, we can swap both of them. We will then compare the second item with the third one and continue like this until we reach the last item.

Implementation

Let’s consider a sample array with the following expected output:

• array: [4, 3, 5, 9, 1]
• output: [1, 3, 4, 5, 9]

Here is how the bubble sort will sort this sample array step-by-step. Items in bold are those that are being compared.

First iteration:

[4, 3, 5, 9, 1] --> [3, 4, 5, 9, 1], 4 > 3 so swap

[3, 4, 5, 9, 1] --> [3, 4, 5, 9, 1], 4 < 5 so no swapping

[3, 4, 5, 9, 1] --> [3, 4, 5, 9, 1], 5 < 9 so no swapping

[3, 4, 5, 9, 1] --> [3, 4, 5, 1, 9], 9 < 1 so swap

Second iteration

[3, 4, 5, 1, 9] --> [3, 4, 5, 1, 9], 3 < 4 so no swapping

[3, 4, 5, 1, 9] --> [3, 4, 5, 1, 9], 4 < 5 so no swapping

[3, 4, 5, 1, 9] --> [3, 4, 1, 5, 9], 5 > 1 so swap

[3, 4, 1, 5, 9] --> [3, 4, 1, 5, 9], 5 < 9 so no swapping

Third iteration

[3, 4, 1, 5, 9] --> [3, 4, 1, 5, 9], 3 < 4 so no swapping

[3, 4, 1, 5, 9] --> [3, 1, 4, 5, 9], 4 > 1 so swap

[3, 1, 4, 5, 9] --> [3, 1, 4, 5, 9], 4 < 5 so no swapping

[3, 1, 4, 5, 9] --> [3, 1, 4, 5, 9], 5 < 9 so no swapping

Fourth iteration

[3, 1, 4, 5, 9] --> [1, 3, 4, 5, 9], 3 > 1 so swap

[1, 3, 4, 5, 9] --> [1, 3, 4, 5, 9], 3 < 4 so no swapping

[1, 3, 4, 5, 9] --> [1, 3, 4, 5, 9], 4 < 5 so no swapping

[1, 3, 4, 5, 9] --> [1, 3, 4, 5, 9], 5 < 9 so no swapping

Fifth iteration

[1, 3, 4, 5, 9] --> [1, 3, 4, 5, 9], 1 < 3 so no swapping

[1, 3, 4, 5, 9] --> [1, 3, 4, 5, 9], 3 < 4 so no swapping

[1, 3, 4, 5, 9] --> [1, 3, 4, 5, 9], 4 < 5 so no swapping

[1, 3, 4, 5, 9] --> [1, 3, 4, 5, 9], 5 < 9 so no swapping

As you can see in the $4^{th}$ iteration, the array is already sorted, but the algorithm does not know if it is complete. The algorithm needs one whole pass without any swap to know it is sorted. You will see the reason in the $5^{th}$ iteration.

Pseudocode

I always see pseudocode as a good way to write my thoughts on an algorithm in plain English before writing it in a real programming language. This is what I call the pseudocode notation (example below):

function bubbleSort(arr)
Set isSwapped to true
WHILE isSwapped = true
    Reset isSwapped to false
    FOR each item in the arr
        IF current item > next item
            swap items
            Reset isSwapped to true
        ENDIF
    ENDFOR
ENDWHILE
RETURN arr

You can read a post I wrote about pseudocode here.

Let’s translate our pseudocode into JavaScript.

Code

Nothing tricky here – I simply used a while loop and preferd to use forEach to iterate over the passed array.

Complexity analysis

To end our journey, let me say just one word about the performance of this algorithm.

Bubble sort is a very simple sorting algorithm, but it is too slow. For this reason, you’ll almost never find or use it in the real world. In fact, it is mostly used for educational purposes.

• Worst Case Time Complexity, aka Big-O: $O(n^2)$
• Best Case Time Complexity, aka Big-omega: $O(n)$
• Average Time Complexity, aka Big-theta: $O(n^2)$
• Space Complexity: $O(1)$