Algorithms in JavaScript
Sort a Array with a QuickSort Function in JavaScript
Quicksort is a sorting algorithm that is much faster than selection sort. Quicksort involves working with two subarrays as well as a pivot item. When implemented properly it's on average Big O notation is O(n log n). Let’s explore this function and recreate it to sort a array within JavaScript!
Instructor: [00:00] Quick sort is a much faster sorting algorithm than selection sort. It's frequently used in real life and is built into some languages like C automatically. It's a divide-and-conquer function that uses recursion to break down the array into smaller pieces, then connects them at the end.
[00:15] The three fundamental components of quick sort is working with an array that holds the elements less than the chosen pivot element. The pivot element and then the array of elements that holds the elements greater than the pivot element.
[00:27] Let's begin by defining the base case of our recursion quick sort, which is going to be if our array is less than two, let's return that array. This is because if our array has one or zero elements in it, then there's nothing to sort. Now we can work on getting to this base case with the least amount of recursion calls.
[00:45] Next up, we'll define our pivot index by saying math dot floor, array dot length divided by two. Then let pivot equals array at that pivot index.
[00:55] You'll find that the most complex issue in quick sort is choosing a good pivot element. Choosing the wrong one can drastically decrease its performance. If at each step we choose the middle as the pivot, then we'll get to the result the quickest. We'll talk about this more after we finish out the function.
[01:12] Next up is creating our less than and greater than arrays that we'll push into. We'll do the actual looping over each element in the array. Do a let I in array. If our I does not equal our pivot index, then we're going to check for this value against the pivot. If it's greater, then we're going to push into the greater array. If it's less than, we're going to push this value into the less than array.
[01:35] We'll close out our function by returning a new array, spreading out the results of calling quick sort on the less array, the pivot, and then spreading the results of quick sort on the greater array. With a quick console log calling our quick sort and some dummy items inside of array, we'll see that this quick start function is working properly. Let's go back and review what we've done so far.
[01:56] First, we're choosing the middle element in our array using math.floor so we don't get a decimal index number and using that as our pivot. This means that each recursive call which breaks down our array into smaller pieces will always use the middle index. Then we have an array that holds the value smaller than the pivot and the items greater than the pivot.
[02:17] We figure this out by using this ternary here. Since we're already adding the pivot item in our return, the if check makes sure we're not adding the pivot item twice.
[02:27] I as a string and pivot index as a number, which is why we use the exclamation mark equals and not exclamation mark equals equals. Finally, in the return is where we are recursively calling our quick start function to then sort the number smaller than our current pivot and items greater than our pivot.
[02:45] Inside of these function calls, our function picks a new pivot by finding the middle and creating two arrays and so on and so forth. Until we get down to our base case and return all of the results back up.
[02:58] Let's talk big O notation and the importance of the pivot element. When it comes to sorting, every single item in the array needs to be touched. We need to see how large or small an item is in order to know where it fits in line.
[03:10] We know we're at least going to be O to N. What makes the algorithm faster is choosing the least amount of pivot items. The more pivot items we have, the larger our call stack gets. That height of our call stack at best case -- which is also the average case -- is getting O log in, which makes our final notation O N log in.
[03:30] Worse case is having a pivot item for every single item in our array, which would give us O N again or O N squared. Let's put a console log inside of the function to see how many times it gets called, and then we'll play around with two different types of pivot indexes. We'll do the last element and the first element in the array. Then we'll console log our pivot so we can count how many times we're pivoting.
[03:53] We see that by using the middle item as our pivot, we have a total of four items. If we instead always use the last element as the pivot, we see that we end up having five pivots and our functions called a lot more. If we use the first item we're back to four and back to the same amount of calls as using the middle.
[04:14] In this one set of numbers, using the middle and the first was the best. You'll find though that if you were to rearrange the numbers, you could find when the last element is better than the first or middle. There are multiple variables that effect the call stack height.
[04:28] Though using the first or the last will give you the worst case big O notation of O N squared when you're trying to sort an array already sorted, we see that we're at five pivot items for using the first item. We still have five if we use the last.
[04:42] However, if we use the middle we only have three. This is the same if we use the numbers flipped, where we go down from six to one. We still have five for the first and we'll have five for the last but only three for the middle.
[05:01] If you use a random pivot index or the middle index, you will, on average, get the best-case scenario.
@Nicholas, it's a vscode plugin called Quokka.js
Why do you use for(let i in array) instead of forEach?
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/for...in#Array_iteration_and_for...in
Using for...in to iterate over array eliminates the possibility of using strict type checking.
here's a beautiful more functional version with ramda:
import { gt, partition } from "ramda";
function quickSort(list) {
if (list.length === 0) {
return list;
} else {
const [pivot, ...rest] = list;
const [left, right] = partition(gt(pivot), rest);
return [...quickSort(left), pivot, ...quickSort(right)];
}
}
const result = quickSort([4, 7, 9, 1, 0, 8, 6, 10, 3, 8, 2, 5]);
console.log(result); // => [0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10]
https://codesandbox.io/s/quicksort-in-ramda-m4br7
Hi Tyler, Firstly, excellent explanation of Big O notation in a relevant way to us JS devs. Secondly, what setup or plugin are you using to display the console logs inline in the editor for an unsaved file? Nicholas.