Who else wants to learn the most efficient implementation of Bubble Sort today.

Even the best engineers struggle to pass technical interviews.

For many, the biggest challenge isn’t writing algorithm but rather writing an efficient algorithm.

Let’s learn the most efficient implementation of Bubble Sort.

What is sorting ?

Sorting is the process of rearranging the items in a collection so that item is in some kind of order. ie: – ascending, descending

Why do we need to learn sorting algorithms?

There are many many ways to sort arrays and each method has its own advantages and disadvantages.

Any particular sorting algorithm can be efficient in any case.

What is a Bubble Sort?

Bubble Sort is a sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

Why bubble sort is named so?

Its named bubble sort because elements in arrays move up into the correct order like bubbles rising to the surface of the water.

Step by step pictorial presentation of Bubble Sort
Source of this image: w3resource

Let’s Write a JavaScript function to apply Bubble Sort algorithm.

Implementation (Worst Case)

// Implementation Step By Step Process
// Step 1 - Start looping from with a variable called i from to beginning to end

// Step 2 -  Start an inner loop with a variable called j from the beggining until i

// Step 3 - if arr[j] is greater than arr[j + 1] than we need to swap two values

function bubble_sort(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length; j++) {
            if (array[j] > array[j + 1]) {
                let temporary = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temporary;
            }
        }
    } return array;
}

bubble_sort([37, 29, 45, 8])
// Expected Output - [8, 29, 37, 45]



But, there is a problem with above implementation that is efficiency,

function bubble_sort(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length; j++) {
   // let's print steps and what we are comparing it to.
            console.log(array, array[j], array[j + 1])        
            if (array[j] > array[j + 1]) {
                let temporary = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temporary;
            }
        }
    } return array;
}

bubble_sort([37, 29, 45, 8])

/*
Expected Output: -
 [37, 29, 45, 8] 37 29
 [29, 37, 45, 8] 37 45
 [29, 37, 45, 8] 45 8
 [29, 37, 8, 45] 45 undefined
 [29, 37, 8, 45] 29 37
 [29, 37, 8, 45] 37 8
 [29, 8, 37, 45] 37 45
 [29, 8, 37, 45] 45 undefined
 [29, 8, 37, 45] 29 8
 [8, 29, 37, 45] 29 37
 [8, 29, 37, 45] 37 45
 [8, 29, 37, 45] 45 undefined
 [8, 29, 37, 45] 8 29
 [8, 29, 37, 45] 29 37
 [8, 29, 37, 45] 37 45
 [8, 29, 37, 45] 45 undefined
 [8, 29, 37, 45]
*/

In the example above you can see we’re comparing 37 29 then 37 45 than 45 8 but then we’re also comparing 45 and undefined at line 22.

When next iteration starts at line 23, We’re comparing 29 and 37, then at line 24 we’re comparing 37 and 8, which will swap.

But, at line 25 we’re trying to sort something already sorted, we know that’s already sorted 45 isn’t moving anywhere.

To make it efficient we need to reduce the number of steps we’re making.

Implementation (Average Case)

We need to do a couple of things to make our algorithm efficient.

1 – what we want to do is basically at the beginning we want to make three comparisons only, we don’t want 45 to get compared with undefined.

2 – And then in the next iteration which starts at line 25, we only want to make two comparisons, because we don’t want to sort something which is already sorted.

Let’s write our algorithm:-

// Step  1 - Start reverse looping from with a variable called i from end to beginning

// Step 2 - Start an inner loop with a variable called j from the beggining until i - 1

// Step 3 - if arr[j] is greater than arr[j + 1] than we need to swap two values

// Step 4 - return the sorted array

function bubble_sort(array) {
    for (let i = array.length; i > 0; i--) {
        for (let j = 0; j < i - 1; j++) {
            if (array[j] > array[j + 1]) {
              
               // let's print steps and what we are comparing it to.
            console.log(array, array[j], array[j + 1])
                let temporary = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temporary;
            }
        }
    } return array;
}

bubble_sort([37, 29, 45, 8])


/* 
Expected Output: -

 [37, 29, 45, 8] 37 29
 [29, 37, 45, 8] 37 45
 [29, 37, 45, 8] 45 8
 [29, 37, 8, 45] 29 37
 [29, 37, 8, 45] 37 8
 [29, 8, 37, 45] 29 8
 [8, 29, 37, 45]
*/

We’re not done yet, imagine, what if we had already sorted array?

Do we still need to loop through all the elements in array? No right?

Let’s see what happens if we implement this algorithm on an already sorted array.

function bubble_sort(array) {
    for (let i = array.length; i > 0; i--) {
        for (let j = 0; j < i - 1; j++) {            
// let's print steps and what we are comparing it to.
            console.log(array, array[j], array[j + 1])

            if (array[j] > array[j + 1]) {
                let temporary = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temporary;
            }
        }
    } return array;
}

bubble_sort([1, 2, 3, 4, 5])


/*
Expected Output: -

 [1, 2, 3, 4, 5] 1 2
 [1, 2, 3, 4, 5] 2 3
 [1, 2, 3, 4, 5] 3 4
 [1, 2, 3, 4, 5] 4 5
 [1, 2, 3, 4, 5] 1 2
 [1, 2, 3, 4, 5] 2 3
 [1, 2, 3, 4, 5] 3 4
 [1, 2, 3, 4, 5] 1 2
 [1, 2, 3, 4, 5] 2 3
 [1, 2, 3, 4, 5] 1 2
 [1, 2, 3, 4, 5]


*/

Did you saw, what just happened, it started looping again, even though the array was sorted.

Implementation (Best Case)

Now, let’s write our last and most efficient algorithm for bubble sort.

function bubble_sort(array) {
    let noSwaps;
    for (let i = array.length; i > 0; i--) {
        noSwaps = true;
        for (let j = 0; j < i - 1; j++) {
            // let's print steps and what we are comparing it to.
            console.log(array, array[j], array[j + 1])

            if (array[j] > array[j + 1]) {
                let temporary = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temporary;
                noSwaps = false;
            }
        } if (noSwaps) break;
    } return array;
}

bubble_sort([1, 2, 3, 4, 5])

/*
Expected Output: -

 [1, 2, 3, 4, 5] 1 2
 [1, 2, 3, 4, 5] 2 3
 [1, 2, 3, 4, 5] 3 4
 [1, 2, 3, 4, 5] 4 5
 [1, 2, 3, 4, 5]

*/

Closing Notes: –

I hope all of you would have enjoyed reading this article. We at codeum.io always aspire to deliver the best stuff that we can serve to our readers. Your satisfaction is our topmost priority.

In the end, we request you to share this post to all social media platforms of your choice. And please float it into your friend circle as well.

Thanks for reading, If you have any questions , please ask questions in the comments below.

More Posts:-

I Was Scared of JS Promises In 2017, But I’m Super-Brave in 2020 (Learn My Tricks)

Step by Step plan that will Get You From ZERO to PASSING a coding interview (at Google, Facebook, Amazon)

Calling All New Developers. Understand How do JS closures work?

The Ultimate Guide to become a full stack web developer in 3 easy step

7 Amazing Array Methods to Boost your Javascript Skills Today

33 Most Powerful linux Commands To Run in Terminal

Who Else Wants to Clear confusion about Javascript Hoisting [Step-by-Step]

Tanisk jha

Mission-Driven Self taught Software Developer with a passion for thoughtful UI Design, collaboration and writing.
Tanisk jha

One thought on “Who else wants to learn the most efficient implementation of Bubble Sort today.

Leave a Reply

Your email address will not be published. Required fields are marked *