JS: Sorting Algorithms, Pt. 2
Alright, part 2 of the sorting algorithms I’m going through. If you missed part 1, read my blog here! In the last blog, I reviewed selection, bubble, and insertion sorting algorithms. All of them required nested loops, which gave them all an O(n²) time complexity. For this one, we’ll be going over ones that are a little better with time complexity, such as O(n log n), which are better for larger datasets.
With the graph above, you can see that there’s some advantage with n log n time complexity, thus a faster execution, which is always important to a computer and a user’s experience.
Heap Sort
This sorting algorithm uses a binary heap to sort through the array. But what is a binary heap?
Binary Heaps
The first rule of this is that it must be a complete binary tree, meaning all nodes are filled on a level before moving on to the next level. If the last level isn’t complete, the nodes should be filled as much as they can from left to right.
With binary heaps, the items in the tree are stored in a special order where the parent node are either greater(max heap) or smaller(min heap) than the values of its two children nodes. With Heap Sort, it builds out a max heap!
First, find the largest value in the array and switch it with the last element of the array and remove it from the heap. Then, repeat this process until there’s only one element left in the array. Then, heapify the root of the tree. Since JS doesn’t have a heap datatype, we’ll need to use a couple functions to make this work. Review the code below:
While this algorithm works, it’s use is limited because the sort algorithms below are easier to understand and are better in practice. So let’s go over them.
Quick Sort
For this algorithm, it takes a ‘divide and conquer’ approach with sorting an array. It would divide elements into smaller parts based on a certain condition and perform sorting operations on the smaller parts. First, an element in the array will be selected as the ‘pivot.’ Next, all array elements will be compared with the ‘pivot’ and arranged where those that are valued less will be to the left of the pivot and those valued more will be to the right. Lastly, the same operations will be performed on the elements that were placed to the left and to the right of the pivot.
Choosing which element is the pivot will determine how this type of sorting takes place. The pivot can be the first, last, middle, or random element of the array. For my example, I’ll choose the middle element as the pivot. Review the code below:
Merge Sort
Like Quick Sort above, this sorting algorithm works by splitting the array in halves and calling itself on the halves. Once the array is split into multiple arrays with a single element in them, then a merge function will build them all back together into a sorted array. Typically, the time complexity is O(n log n), but there are other circumstances for different time complexities. Review the code below:
Merge sort is my go-to sort algorithm as it has an O(n log n) time complexity and it’s easy to understand and to teach. Like stated before, there are many more sorting algorithms out there. Find what best works for you!
Resources:
- “Sorting Algorithms Explained,” FreeCodeCamp, accessed October 15, 2020, https://www.freecodecamp.org/news/sorting-algorithms-explained/
- “JS: Sorting Algorithms”, accessed October 15, 2020, https://khan4019.github.io/front-end-Interview-Questions/sort.html
- “Time Complexities of all Sorting Algorithms,” GeeksForGeeks, accessed October 15, 2020, https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/
- “Heap Sort,” GeekForGeeks, accessed October 17, 2020, https://www.geeksforgeeks.org/heap-sort/
- “Heapsort for Javascript Newbies”, GitConnected, accessed October 17, 2020, https://levelup.gitconnected.com/heapsort-for-javascript-newbies-598d25477d55
- “Quick Sort,” GeekForGeeks, accessed October 16, 2020, https://www.geeksforgeeks.org/quick-sort/
- “Merge Sort,” GeekForGeeks, accessed October 16, 2020, https://www.geeksforgeeks.org/merge-sort/
