Recursively Sort an Array in JavaScript with Quick Sort
Quick sort is another "divide and conquer" algorithm, calling itself recursively to sort our list. With quick sort, we pick an index of our array to be the "pivot". Every item is compared to the pivot, and pushed into a left or right array depending on that comparison. Quick sort is then called on these left and right arrays.
This is an efficient algorithm and uses less memory than merge sort. The time complexity of quick sort is O(n log(n)). Sorting any list requires at least one pass through the entire list, hence n, but increasing the size of our list doesn't lead to a linear or quadratic increase in operations. Each doubling in size only results in one more level of operations.
Instructor: [00:01] QuickSort is a recursive sorting algorithm. We take our original array, breaking it down into smaller arrays to sort, calling QuickSort again on the smaller arrays. In particular, QuickSort uses the concept of a pivot.
[00:14] We pick one item. It could be at the head or the tail or somewhere in the array -- so long as it's consistent -- and then we compare each item to that pivot. If it's less than the pivot, we're going to push it into a left array. If it's more than the pivot, we're going to push it into a right array.
[00:30] We then call QuickSort on those sub-arrays, merging them together, returning the array that's the result of QuickSort on the left, the pivot, and QuickSort on the right.
[00:39] We'll make a function QuickSort to create our algorithm. QuickSort receives an array as an argument and will return an array as well. In this algorithm, we'll return a new array of sorted items, so for now, we'll return an empty array.
[00:53] Next, since we know we will call QuickSort recursively, we need to establish our base case to prevent a stack overflow. If the array length is less than two, we want to return that array.
[01:06] Now that we've finished our base case, what we want to do is establish our pivot. We'll use the last item in the array as our pivot. Since I'll need the pivot index later in the algorithm, I'm going to store that as a variable and derive the pivot from that.
[01:20] I'll also create empty arrays for our left and right sub-arrays. We're going to push items into these arrays in just a moment. We'll create a four-loop that will iterate through every item in the array up to the pivot, hence, why we stored the pivot index.
[01:35] For each item in our loop, we want to compare that current item to our pivot item. I'm going to store our current item as a variable. If the current item is less than the pivot, we'll push it into the left array, otherwise, we'll push it into the right array. With our loop done, we now want to call QuickSort recursively on our left and right arrays, placing our pivot in the middle.
[02:00] Now that we've finished our algorithm, I want to add a way to visualize what's going on within it. I'm going to use the Print Array utility that I've imported at the top of this file and place it inside of QuickSort.
[02:13] Now that we can visualize what's taking place in our algorithm, let's create an array of unsorted numbers and pass that to QuickSort. We'll save that and log it into our terminal and see what happens. Our first printout of the array is the complete unsorted array, and our pivot was four because it's the last item.
[02:32] The first array we see called recursively is all the items less than four -- that's three, two, one. The pivot was one, thus we got three, two. The pivot was two, and we ended up with three as the final one because it was the only one we had available.
[02:45] The next sub-array was everything left that was put into the right array -- 10, 6, 7, 9, 8, 5. Five is our pivot. Everything is greater than that, so that was put into another array, and it continues to break down. What this doesn't show us, though, is what our sorted array was.
[03:02] A quick way for us to fix this is to store our returned array as a variable and log out that returned array and just see that again. I'm going to call this one more time. We can see how it starts to stitch them back together.
[03:17] If we come back out, we see how they were divided, continue to be divided. Now that we get down to 10, we start to see them get stitched back up.
[03:26] You can even see that four wasn't used in any of these iterations until the very final one, because it was the original pivot of our whole algorithm.