Bubble sort algorithm in javascript

A simple implementation of bubble sort algorithm in javascript.

Bubble sort is the simplest sorting algorithm which arranges the number in increasing or decreasing order by repeatedly swapping the adjacent elements if they are in the wrong order.

This is repeated until all the elements are sorted in the required order.

Example

Input:
[-5, 2, 33, 10, -7]

Output:
//Sorted in ascending order
[-7, -5, 2, 10, 33]

This is how the bubble sort algorithm works

Bubble sort implementation in javascript

• We are going to use two nested loops to sort the array in the given order.
• The inner loop will loop till the length of the first loop and swap the elements which are in the wrong order.
• This will be repeated until all the elements of the array are sorted.
• We will ES6 array destructuring for swaping two elements.

//Bubble sort
let bubbleSort = (arr) => {
  //Length of the array
  let n = arr.length;
  
  for(let i = 0; i < n - 1; i++){
    for(let j = 0; j <= n - i - 1; j++){
        //Swap the numbers
        if(arr[j] > arr[j+1]){
          [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
        }
    }
  }
  
  return arr;
}

Input:
console.log(bubbleSort([-5, 2, 33, 10, -7]));

Output:
[-7, -5, 2, 10, 33]

Time complexity: O(n ^ 2).
Space complexity: O(1).

---

Optimized Bubble sort

The above implementation works fine but always run in O(n ^ 2) time, even if the array is already sorted.

We can optimize the same by adding a flag which will stop the inner loop if there is no swapping of elements(Which means all elements are sorted).

//optimized bubble sort
let optimizedBubbleSort = (arr) => {
  //Length of the array
  let n = arr.length;
  
  //Flag to check if swap 
  //is performed in inner loop
  let swapped = false;

  for(let i = 0; i < n - 1; i++){
    for(let j = 0; j <= n - i - 1; j++){
        //Swap elements
        if(arr[j] > arr[j+1]){
          [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
          //Set the flag to true if swapped
          swapped = true;
        }
    }
    
    //If not swapped then break the loop
    if(!swapped){
      break;
    }
  }
  
  return arr;
}

Input:
console.log(optimizedBubbleSort([-5, 2, 33, 10, -7]));

Output:
[-7, -5, 2, 10, 33]

Time Complexity Of Bubble Sort

---

Space Complexity Of Bubble Sort

• Average and Worst case sorting occurs when arrays are reverse sorted, Best case sorting occurs when arrays are already sorted.
• Sorting In place: Yes. It does not uses extra space to sort the elements.
• Stable: Yes. It is stable sorting algorithm.

Due to its simplicity, it is always used to introduce the concept of sorting. But it is the worst performer than all the sorting algorithms out there.

Recursive Bubble Sort.

Other sorting algorithms

• Selection Sort
• Insertion Sort
• Recursive Insertion Sort