The Bubble Sort algorithm is a very interesting question that you may have heard in your school or college asked in many interviews including FAANG companies.

Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they are in the intended order.


Just like the movement of air bubbles in the water that rise up to the surface, each element of the array move to the end in each iteration. Therefore, it is called a bubble sort.


Bubble Sort Working:


1. First Iteration (Compare and Swap)

  1. Starting from the first index, compare the first and the second elements.
  2. If the first element is greater than the second element, they are swapped.
  3. Now, compare the second and the third elements. Swap them if they are not in order.
  4. The above process goes on until the last element.

2. Remaining Iteration

  1. The same process goes on for the remaining iterations.
  2. After each iteration, the largest element among the unsorted elements is placed at the end.
  3. In each iteration, the comparison takes place up to the last unsorted element.
  4. The array is sorted when all the unsorted elements are placed at their correct positions.


Let's start with the algorithm,

var bubbleSort = function(array){
    for(var i = 0; i <= array.length-1; i++){
        // Last i elements are already in place
        for(var j = 0; j < ( array.length - i -1); j++){

            // Comparing two adjacent numbers 
            // and see if first is greater than second
            if(array[j] > array[j+1]){

            // Swap them if the condition is true 
            var temp = array[j]
            array[j] = array[j + 1]
            array[j+1] = temp
            }
        }
    }
    return array;
}


Time Complexities:

  • Worst Case Complexity O(n2): If we want to sort in ascending order and the array is in descending order then the worst case occurs.

  • Best Case Complexity O(n): If the array is already sorted, then there is no need for sorting.

  • Space Complexity O(n2):  Space complexity is O(1) because an extra variable is used for swapping. In the optimized bubble sort algorithm, two extra variables are used. Hence, the space complexity will be O(2).


I hope you understood the algorithm. If you have any doubts, please let us know in the comments.