JavaScript Algorithms #1- Bubble Sort

1. What is Sorting?

Sorting is the process of rearranging the elements in a data structure(e.g. array) so that the elements are in order. JavaScript offers a built-in method Array.prototype.sort() which allows us to sort the elements of an array easily. The sort() method returns the sorted array in alphabetical and ascending order. However, while it works well with the string, sorting numbers with this method can produce incorrect results as sort() method converts every type of elements into strings and then compare their sequences of UTF-16 code unit values for sorting. We could use a compare function to fix this but there are many other efficient ways to sort the data. Bubble sort is one of those.

2. What is Bubble Sort?

Bubble sort is a sorting algorithm where the largest values bubble up to the top. Bubble sort compares two adjacent elements and swaps them until they are not in the intended order, so each element of the array moves to the end in each iteration just like the bubbles in a glass rise up to the surface.

3. Bubble Sort Pseudo Code

1. Start looping the array with a variable called i.
2. Start an inner loop from the beginning until (array.length - 1 - i) with a variable j. We don't have to iterate until the end because when the j reaches the final element, it doesn't have the right(next) element to compare with(therefore (array.length - 1)). Also, we should minus i from the (array.length - 1), because after the each iteration of i, the number of i elements will be locked at the end. We don't have to do anything with the already sorted elements.
3. If array[j] is greater than array[j+1], swap those two values.
4. Return the sorted array.

   4. Implementing the Bubble Sort

function bubbleSort(array){
               const arr = array.slice(); //making a shallow copy of array using slice() method to make it a pure function(so that it doesn't affect the original array)

               for (let i = 0; i < arr.length; i++){
                   for (let j = 0; j < arr.length - 1 - i; j++){
                       if (arr[j] > arr[j+1]){
                         [arr[j], arr[j+1]] = [arr[j+1], arr[j]]; //let temp = array[j]; array[j] = array[j+1]; array[j+1] = temp
                       }
                   }
               }
               return arr;
           }

5. Optimizing the Code

To make the bubble sort more efficient, we need a new variable. This variable will tell us whether the swap has occurred. If the swap hasn't occurred, we'll just break out of the loop because no swap means the array has already been sorted properly. Let's call this variable 'noSwap' and make its default value 'true'. If the swap happens, change its value to 'false'. If the value of 'noSwap' is true after the iteration, just break out of the loop.

function bubbleSort(array){
               const arr = array.slice()
               let noSwaps; 
               for (let i = 0; i < arr.length; i++){
                   noSwaps = true;
                   for (let j = 0; j < arr.length - 1 - i; j++){
                       if (arr[j] > arr[j+1]){
                         [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
                         noSwaps = false;
                       }
                   }
                   if (noSwaps) break; //if (noSwaps === true) break;
               }
               return arr;
           }

6. Time Complexity of the Bubble Sort

In the worst case scenario, the complexity of bubble sort will be O(n²) because we have nested loop. But in the best case scenario or using our optimized version, it could be more like a linear search O(n).