Elementary Sorting in JavaScript

Hi guys, in this blog we will discuss in details on several elementary sorting algorithm in JavaScript .

So we are having many sorting algorithms but in this blog we will discuss on the very basic and simple sorting algorithm which are :

1 > Bubble Sort

2> Insertion Sort

3> Selection Sort

So let’s start the discussion :

What is Sorting ?

Sorting is the process of rearranging the items in a collection (e.g. an array) so that the items are in some kind of order, for example :

• Sorting numbers from smallest to largest
• Sorting names alphabetically
• Sorting movies based on release year
• Sorting movies based on revenue, etc

Why we need to learn this sorting ?

In the current scenario of online website and shopping , user want to get everything sorted on their finger tip , Like if we take an example of any shopping website , almost all the website are competing on making their websites more and more user friendly, sorting plays an important role to achieve it , like offering more and more sorting options to the user on their product listing page . Sorting is an incredibly common task, so it’s good to know how it works. There are many different ways to sort things, and different techniques have their own advantages and disadvantages. Sorting sometimes has quirks, so it’s good to understand how to navigate through them and determine which sorting algorithm is suitable for which scenario .

Javascript has a sort method , Yes it does !!, but it doesn’t work the way we expect it to work .

So if we see the above function , it returns the sorted result , but if we see the next function

It’s not returning sorted array . This is happening because by default, the sort() function sorts values as strings. This works well for strings but numbers are sorted as strings which is not correct.

So let’s see how JavaScript sorts :

The built-in sort method accepts an optional comparator function, we can use this comparator function to tell JavaScript how you want it to sort, the comparator looks at pairs of elements (a and b), determines their sort order based on the return value. If it returns a negative number, a should come before b, If it returns a positive number, a should come after b, and If it returns 0, a and b are the same as far as the sort is concerned. Let’s try to understand it with an example :

function numberCompare(num1, num2) {
  return num1 - num2;
}

[ 6, 4, 15, 10 ].sort(numberCompare);
// [ 4, 6, 10, 15 ]

So here the comparator function is numberCompare function , if we want to arrange the number in ascending order we returning the value of a - b . If a is greater than b , it will give positive value , which means a will come after b, and the array will get sorted in ascending order.

Now let see a string example:

function compareByLen(str1, str2) {
  return str1.length - str2.length;
}

[ "Steele", "Colt", "Data Structures", "Algorithms" ]
  .sort(compareByLen);
// [ "Colt", "Steele", "Algorithms", "Data Structures" ]

So here comparator function is compareByLen function , here we want to arrange strings in ascending order of string length , so in compareByLen function we are returning the difference of str1 and str2 , if str length is greater than str2 , then the str1 will be placed after str2.

Before going to sorting part we should have understanding of swapping . Because sorting involves many swapping .

// ES5
function swap(arr, idx1, idx2) {
  var temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

// ES2015
const swap = (arr, idx1, idx2) => {
  [arr[idx1],arr[idx2]] = [arr[idx2],arr[idx1]];
}

So these are the two ways by which we can perform swapping first one is by using a third parameter temp , and second one is ES2015 way of implementing the same logic.

Bubble Sort :

A sorting algorithm where the largest values bubble up to the top!

So let’s take an example [5 , 3 , 4, 1 , 2] , we will first check first two numbers 5 , 3 and compare if 5 is greater than 3 , then we are swapping the position of each other, it will become [3 , 5 , 4 , 1 , 2] , then we will again compare 5 and 4 , since 5 is greater than 4 , we will again swap them so now array will be [3 , 4 , 5, 1 , 2] , then we will compare 5 and 1 , since 5 is greater than 1 , we will again swap 5 and 1 so array will become [3 , 4 , 1 , 5 , 2 ] , similarly we will compare 5 and 2 , since 5 is greater than 2 , we will swap 5 and 2 , so array will become [3 ,4, 1, 2 ,5 ] similarly we will iterate through the array again from the beginning and place the next highest value before 5. And once these whole cycle completes we will get the array sorted in ascending order .

Now let’s see the pseudocode for Bubble Sort:

• Start looping from with a variable called i the end of the array towards the beginning
• Start an inner loop with a variable called j from the beginning until i - 1
• If arr[j] is greater than arr[j+1], swap those two values!
• Return the sorted array

Now let’s see two approach one is unoptimised and another is optimised :

// UNOPTIMIZED VERSION OF BUBBLE SORT
function bubbleSort(arr){
  for(var i = arr.length; i > 0; i--){
    for(var j = 0; j < i - 1; j++){
      console.log(arr, arr[j], arr[j+1]);
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;         
      }
    }
  }
  return arr;
}

// ES2015 Version
function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

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

bubbleSort([8,1,2,3,4,5,6,7]);

In this function bubbleSort we are accepting an array , so we are running a loop from end to beginning that is from array length to 0 , and inside that we are running a loop from starting to end until i -1, so we are checking if array[j] is greater than array[j+1], if it’s true we are swapping both the values. So we have shown both normal and ES2015 way of swapping variables. And by this we will get the array sorted in ascending order . But there is a issue if you have noticed we are doing some unnecessary comparing which are actually not required , like let’s see an example we are having array [ 5 , 3 , 4 , 1 , 2 ] and we have almost sorted the array by following this algorithm, let’s assume we are in this stage where array looks like [ 2 , 1 , 3 , 4 , 5 ] , now if we take 2 and start comparing it with other elements like first with 1 , since 2 is greater than 1 , we will swap position of 2 and 1 , and it will look like [ 1, 2 , 3 , 4 , 5 ] now if we compare 2 and 3 , since 2 is smaller than 3 , we will skip the swapping then we will again compare between 3 and 4 then 5 , since the array is almost sorted so we would have easily skip those comparison. So we can say the above is not totally optimised , let see more optimised solution.

// Optimized BubbleSort with noSwaps
function bubbleSort(arr){
  var noSwaps;
  for(var i = arr.length; i > 0; i--){
    noSwaps = true;
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps = false;         
      }
    }
    if(noSwaps) break;
  }
  return arr;
}

bubbleSort([8,1,2,3,4,5,6,7]);

Let’s see more optimized approach of bubbleSort , where we are setting a new variable noSwaps which will consider whether any further comparison is required for the current iteration, so for each iteration we are setting noSwaps to true at beginning . Then we are starting the iteration , we are setting it to false if and only if the arr[j] > arr[j-1] else we will break out from that iteration , by this we will be avoiding any further comparison , if we find any number which is greater than the selected number while iterating , we will omit further comparison for current iteration .

Time and Space Complexity for Bubble Sort :

In best case scenario , the time complexity of bubble sort will be O(n) , and in both average and worst case , the time complexity of bubble sort will be O(n²). Space complexity of bubble sort will be O(1). Now let’s come on to our next sorting algorithm selection sort.

Selection Sort :

Similar to bubble sort, but instead of first placing large values into sorted position, it places small values into sorted position. Let see this by an example : we are having an array [5 , 3 , 4 , 1 , 2] , so we will start finding the smallest element in each iteration , first we will consider the first element as the smallest element , 5 is the smallest element , now we will move forward and check whether 3 is lesser than 5 , since it’s true we will set 3 as smallest element and will continue comparing 3 with other numbers as well , at the end of the iteration we will find 1 as the smallest element , and we will swap the position of smallest element (1) and first element (5) so the array will look like this- [ 1 , 3 , 4 , 5 , 2 ] , next iteration we will start from 1 index for searching for next smallest element since 0 index is already sorted , so at the end of whole cycle of iteration the array will be sorted in ascending order.

Now let’s see pseudocode for Selection sort:

• Store the first element as the smallest value you’ve seen so far.
• Compare this item to the next item in the array until you find a smaller number.
• If a smaller number is found, designate that smaller number to be the new “minimum” and continue until the end of the array.
• If the “minimum” is not the value (index) you initially began with, swap the two values.
• Repeat this with the next element until the array is sorted.

Now let’s see the coding part of the same :

// LEGACY VERSION (non ES2015 syntax)
function selectionSort(arr){
    for(var i = 0; i < arr.length; i++){
        var lowest = i;
        for(var j = i+1; j < arr.length; j++){
            if(arr[j] < arr[lowest]){
                lowest = j;
            }
        }
        if(i !== lowest){
            //SWAP!
            var temp = arr[i];
            arr[i] = arr[lowest];
            arr[lowest] = temp;
        }
    }
    return arr;
}

// ES2015 VERSION
function selectionSort(arr) {
  const swap = (arr, idx1, idx2) =>
    ([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);

  for (let i = 0; i < arr.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[lowest] > arr[j]) {
        lowest = j;
      }
    }
    if (i !== lowest) swap(arr, i, lowest);
  }

  return arr;
}

selectionSort([0,2,34,22,10,19,17]);

SelectionSort function accepts array input , inside that function we are looping through the array , and we are considering the the first element as the smallest element , in first iteration i will be 0 , we are running a loop j from i+1 to arr.length , there we are simply finding the smallest element in the array , once the we get the smallest element we are swapping the position of smallest number and Ith element in first iteration which is nothing but 0th element , again we will be doing the same to 1st element in second iteration and swap the position between smallest element and ith element and at the end of the whole iteration we will have the array sorted in ascending order.

Time and Space Complexity for Selection Sort :

In best case scenario , the time complexity of selection sort will be O(n) , and in both average and worst case , the time complexity of bubble sort will be O(n²). Space complexity of selection sort will be O(1). Now let’s come on to our next sorting algorithm insertion sort.

Insertion Sort:

In insertion sort we are building up the sorted array by gradually creating a larger left half which is always sorted . Let see an example :

Let see we are having array [ 5 , 3 , 4 , 1 , 2 ] , so we will pick up second element 3 in the array , then we will compare the second element with the one before it (5) and swap it to make it sorted , it will look like this now [3 , 5 , 4 , 1 , 2] , then we will take next element 4 , compare it with 5 , swap both since 4 is less than 5 , then we will not swap since 4 is not less than 3 , so now the array will look like this [ 3 , 4 , 5 , 1 , 2 ] , then we will take 1 and compare it with 5 and swap , since 1 is less than 5 , similarly it will be compared with 4 and 3 and placed in the 0th position , now the array will look like this [1 ,3 , 4 , 5 , 2] and finally in similar way we will take 2 and place it in the right position and will get a sorted array [1 , 2 , 3 , 4 , 5].

Let’s see pseudocode for Insertion Sort :

• Start by picking the second element in the array
• Now compare the second element with the one before it and swap if necessary.
• Continue to the next element and if it is in the incorrect order, iterate through the sorted portion (i.e. the left side) to place the element in the correct place.
• Repeat until the array is sorted.

Now let’s see the coding part of the same :

function insertionSort(arr){
 var currentVal;
    for(var i = 1; i < arr.length; i++){
        currentVal = arr[i];
        for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal;
    }
    return arr;
}

insertionSort([2,1,9,76,4])

In this code we are defining a function insertionSort which accepts an array, we have declared a variable currentVal where we will store the value of the element which we will pick to make it sorted , so we are running a loop from 1 to end , where we are first storing the 1th element in currentVal , then we are running another loop from i-1, and checking adding if j≥0 and arr [j] >currentVal , we will replace arr[j+1] with arr[j] else we will make arr[j+1]= currentVal , and finally we will return sorted array .

Time and Space Complexity for Insertion Sort :

In best case scenario , the time complexity of insertion sort will be O(n²) , and in both average and worst case , the time complexity of insertion sort will be O(n²). Space complexity of insertion sort will be O(1).

Conclusion:

In this blog we have discussed very basic and fundamental sorting algorithm and we got the significants of sorting . But for industrial fulfillments Bubble sort, selection sort, and insertion sort are all roughly equivalent because all of the algorithm are having average time complexities which are quadratic. So we can do better…but we need more complex algorithms! which we will discuss in our upcoming blogs :)

Please refer to this link to get a visual representation of all sorting algorithms:

Sorting Algorithms Animations

And please checkout my GitHub repo as the reference for the coding discussed in this blog :

GitHub - Yudhajitadhikary/Searching-and-Elementary-Sorting: It's a reference of code discussed in…

HAPPY CODING :)