A Guide To Sorting Algorithms in JavaScript

December 25, 2018 0 Comments

A Guide To Sorting Algorithms in JavaScript

 

 

A bubble sort algorithm is a very common algorithm and is usually one of the first things taught in a computer science class. This is because a bubble sort works in a very similar manner to how we human beings would sort through items.

Let’s start by creating a function named bubbleSort. This function will take in an array as an argument, which it will manipulate in order to sort and then return that array back to us.

In this algorithm, we will create a loop where we compare an item with the next one in the array. If the current item is greater than the next one, then they will get swapped. This loop will keep repeating itself until we come across the scenario where none of the current items are greater than the one next to it. This is why we will use the do while loop instead of a regular while loop.

The do while loop needs an argument that it will check before running. Let’s name this argument as swap and set its initial value as false.

Inside the loop we will check if the current item is greater than the next one in the array. If it is, then we will first store it in a temporary variable, then perform the swap. To indicate that the swap is performed, we will set the value of swap to true.

To test this algorithm, simply create an array of numbers and pass it into the bubbleSort function as shown below:

const nums = [5, 10, 1, 9, 2, 8, 3, 7, 4, 6]
bubbleSort(nums)

In your output, you will notice that the algorithm prints out the end result multiple times before terminating. This is because the algorithm makes one last run across all the elements of the array to make sure that they are sorted properly.

In the insertion sort algorithm, we make the code believe that an item in the array is a sorted list. The algorithm then compares all the items in the array before it and decides where that “sorted list” needs to be inserted in the array.

This may sound a little confusing to you. And it is justifiable since we need to you two loops, one inside another, in order to perform this algorithm.

To start, we will create a function called insertionSort that will take in the array as an argument. We will use nested loops to perform the sorting. Here’s how the loops will work.

First, we will take an element from the array and check if its greater or smaller than the element next to it. The outer for loop will start from the second element of the array and will run for the entire length of the array.

The inner loop will start from the beginning of the array and will run untill the current element of the outer loop. The inner loop will also reset every time the outer loop’s iterating variable’s value increases.

As for the actual sorting, we will compare the outer loops element with the inner loops element. If the outer loop’s element is smaller, then we will move it to the position of the inner loop’s element and vice versa. To do this we will use the array’s slice method.

Let’s use the same array that we used before and test this algorithm

const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
insertionSort(numbers)

And that should work! If you consider the movement of 8, you will notice that starts to stay at the same position for a while, and the duration gets bigger with each iteration. That is because, the algorithm moves through all the items of the array, then increments the value of the outer loop’s iterator, then when it comes across the element 8, it will work on it before moving on to the next element in the array.

Divide and Conquer! This is the principle behind the working of the merge sort algorithm. The algorithm breaks down an array into smaller arrays. It will then sort these smaller arrays as they are quicker due to their smaller size. Finally, the smaller arrays are brought together to gives us the final sorted array.

While the bubble and insertion sort algorithms use iteration, merge sort uses recursion. Recursion is where the function calls itself. Iteration, on the other hand, involves something else in our code running a block of code multiple times.

Here we will divide the array in two parts, which will then be divided into smaller parts, untill we get a set of arrays where each array contains only 2 elements. Then we will sort this small array simply by comparing which element is greater/smaller and join these arrays back again.

Let’s start by creating a function called divide which will receive an array as an argument. The function will then check if the length of the array is already less than 2, because if it is, then don’t need to divide anything, since less than 2 is 1, and you really don’t have anything else in the array to compare with. In this scenario, the algorithm will simply return the same array back to us.

If the array is longer than 2, then we will divide it into two part. First we need to find the middle number of the array. Once we get that, we will use it the splice method to create the two smaller arrays.

We will create another function that does the actual sorting. I will call it…. sort. The sort function will take the two small arrays as arguments and sort each of them individually, and join them together. The function will contain an array where the sorted elements will be stored.

There will be a scenario where we have sorted both the smaller arrays, but there are still elements in the original array left. In such a case, we need to first join the two small arrays together and place the remaining elements in a new array.

We can use the spread operator ( ... ) to “spread” the elements into this new array.

As seen above, we are using the sort function inside the divide function. And, we are passing the divide function as argument to the sort function. A very complex case of Ouroboros.

You can test this algorithm by passing an array of numbers to the divide function.

const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
console.log(divide(numbers))

This is another algorithm that follows the “divide and conquer” method. The algorithm first creates two smaller arrays and also picks an index from the array. All the elements of the array are compared with this element and get pushed into one of the two arrays based on a comparison. The sorting is then done on one of the two arrays.

As with every other algorithm in this post, we will create a function that will take the array of numbers as an input argument. If the array has only one element, sorting can be ignored and the same array can be returned.

We will then choose the element of the array store it in a separate variable. Then, we will create two arrays where the elements will be push after comparing with the last element of the array. For that, we will use a for loop that will iterate through every element in the array.

Similar to mergeSort, we will use the spread operator ( ... ) to insert the elements from the two arrays and the chosen element into a new and final array.

Testing this algorithm with an array of numbers should give us the following output:

const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
quickSort(numbers)
// Output
5 6
3 4 5 6
1 2 3 4 5 6
8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10 // Final Answer

In this post, we have taken a look at some of the well known sorting algorithms in JavaScript. Each of these algorithms comes with their own strengths and weaknesses.

A bubble sort algorithm might be easier to understand, but it is the most inefficient of the four algorithms in this post. If we give it an array of 10 elements, then at worse it will compare every element with every other element in the list, resulting in a maximum of 100 (10*10) loops.

Insertion sort uses two loops. And since these loops are placed one inside the other, the time complexity will be of the form 0(n^2) where n is the number of elements in the array. A silver lining, this algorithm will perform better than bubble sort if the array elements require less sorting.

Merge sort uses recursion, which improves the efficiency of the sorting process by a huge margin. Merge sort requires the algorithm to go through every element of the array at least once. But with each recursive call, we only operate of half the elements. So even if the number of elements increases to twice the original size, the algorithm will only require us to call one more recursion.

Quick Sort is the most efficient algorithm of the four in this post. Similar to merge sort, this algorithm also requires at least one go through the entire array. But any increase in the array’s size will not lead to any kind of increase in operations. Doubling the array size will only cause in one extra level of operation of the algorithm.

Thanks for reading this long post! I hope it helped you understand JavaScript Algorithms a little better. If you liked this post, then please do give me a few 👏 or a shoutout on Twitter. You are welcome to comment and ask anything!


Tag cloud