Sorting Algorithms : Bubble Sort

(Javascript implementation)

3 min readMar 4, 2021

Time Complexity :

Worst Case: O (n²)
If we use our optimized version and the given array is sorted the best case would be O(n).

How it works :

Bubble Sort it’s going to loop through the array and compare two adjacent elements, so it can swap them in case one is bigger than the other.
It will repeat this operation until the array is sorted.

Let’s take this unsorted array and compare the first two elements. For that matter let’s initiate our loop to compare 5 with the rest of values.

Since 5 is greater than 2 we swap this elements too.

Last round of the first loop. Let’s compare the last pair.

Since 5 is greater than 3, we swap them so our first round it’s finished. Now the old first index of the array is sorted. It happened to be the biggest number, so it traveled to the very last index!

Second round! Our new first index is 4, let’s iterate over the array and compare it with the rest of elements step by step.

Sorry… I skipped a few steps, but I think you got the idea. We compared 4 with the other elements and did our swaps until it was sorted. Now we have to take in consideration that the rest of the array is sorted. So it would be nice to tell to our algorithm to stop if there is nothing to swap, or it will be looping and comparing until the end of the algorithm.

Our tiny helper function :

Taking in consideration that we need to swap elements, let’s define a function to accomplish that task.
This “swap” function will take an array and two indexes as a parameters so it can return the array with the modifications.

Option a: This swap function is easy two understand. We will create a temporal variable to store our first element and then swap the elements.

Option b: if you prefer an “one line” solution this will be your perfect match.

Pseudocode :

// Create a variable "i" and start looping from the end of the array 
   towards the begining. 
// We will use this loop to iterate over the array. 
// Doing an inverse loop avoids to iterate over sorted elements.// Create an inner loop using a variable  which runs from the 
   beginning until i-1.
// We will use this inner loop to compare the pairs.// If arr[j] is greater than arr[j+1] swap those elements.

Code :

This is the implementation but with one big caveat. The algorithm will continue running until the outer loops finish all the iterations.

Optimizing our code:

Now we can keep track of our swaps, and if there is nothing else to swap. The algorithm will stop. This will be more time efficient.

Try toplay with the comparison operator at line 11 to achieve an ascending or descending order.

Please, check here the explanation for other basic sorting algorithms :