Implementing Quicksort in JavaScript
In this blog, we implement a Quicksort in JavaScript. Quicksort is an algorithm used to sort arrays with a divide and conquer technique. First, we select a pivot element of the array, in this case the middle element. Next, we swap elements that are greater than or less than the pivot and produce 2 sub-arrays. When successful, the sub-array on the right only contains elements that are greater than the pivot, and the one on the left only contains elements that are less than the pivot. After this step, we know that the pivot element has found its’ final position in the sorted array. We repeat this partitioning process recursively until the base case is reached where sub-arrays produced only contain 1 element, resulting in a sorted array.
Let’s get into some code, first we need to write a partition function. This function will take in the array along with a left and right element. Left and right in this case tell the function which part of the array to focus on sorting. Here’s the function:
Lets step through this code together. First we select the pivot element to be the midpoint of left and right. We then assign i and j to represent left and right. Next we set a condition that i is less than or equal to j while the next code runs. This ensures that as we increment i, it always indicates a position on the left side of the pivot element. Next, we increment i upward until it points to an element of the array that is less than the pivot. After that, we decrement j until it finds an element that is greater than the pivot. We than check to be sure that i is till greater than or equal to j. If true, we swap the elements pointed to by i and j and keep moving through the loop until the condition specified on line 5 is met. We have now successfully arranged the elements such that all of the elements on the left of pivot are less than pivot, and all of the elements on the right are greater than pivot.
Why do we return i? The final value of i indicates the starting point of the next sort necessary with our recursive quick sort technique. Let’s take a look:
Now that we have a working partition function, we can call it recursively until we finish sorting the array. The base case for this will be an array that is 1 element long as prescribed on line 24. First step is to acquire the first i by calling the partition method with the arguments passed into the quickSort function, shown on line 25. Then we call the sub arrays produced with the help of i. So in the if statement on line 26, we run quickSort on the sub array to the right of the original pivot. And in the next if statement on line 29, we run quickSort on the sub array to the right of the original pivot. In this way, we split each sub array in half with each iteration, eventually leading to a completely sorted array which is returned.
It helps when thinking this through for us to visualize an example of the flow that happens as the code runs. So here we start with an array of 10 elements and illustrate how the code in quickSort will split up the array into smaller and smaller pieces until the array length is 1. Also, note that we aren’t actually splitting the array itself, we’re just running the partition method on each corresponding section of the array.
It helps when seeing different algorithms for the first time to get your hands dirty and attempt to code out a solution yourself. Once you’ve done so, it helps to cement the logic in your head for future use. And even when you’re done with that, write a blog and explain it in your own words to further drive home the concept!
