Sorting (Part 6.0): Quick Sort [Sorta Efficient]

Greetings, fellow NBers!

Welcome to my sixth iteration of my sorting series. Today, we'll be discussing a personal favorite: Quicksort, or Quick Sort.

Quick Sort: The Algorithm Under the Hood

Quick Sort is what's called a "divide and conquer" sorting algorithm. It takes a particular approach: pick an element p from the array-to-sort arr, any element, and call that the pivot point. Put all the elements in arr that are less than p on the left side of p, so in arr[0] to arr[k-1], where k is the final position in the sorted array of p. Put all the elements greater than p on the right of p, or in the spots arr[k+1] to arr[n-1], where n is the size of the array.

There are a few ways to accomplish this -- some are more efficient than others. Today, I'll be showing you the easiest way to do it, where we make new arrays for the "left" and "right" parts, and then join them at the end, rather than doing what's called in-place quicksort.

Time Complexity

Mathematically, the worst-case time complexity of Quick Sort is O(n^2), when the array-to-sort is in the worst possible order: reversed.

BUT, Quick Sort often behaves logarithmic-ally, rather than quadratic-ally, meaning it commonly has the time complexity O(n * log(base 2) of n).

So, it is sometimes faster than the previously-covered bubble, insertion, and selection sorts... Don't get too excited, but insertion sort is coming back for a little cameo in a coming post...

Ruby Implementation

Here is the pastebin link; screenshots:

Okay, so our quicksort(...) function starts on line 6. The first thing you see is our declaration of strlen. On line 10, we check if str, our array-to-sort, is empty or only has one element. An array with one or fewer elements is always sorted, so we just return the original array.

On line 13, we hold the value of our pivot in pivot_char by accessing the value stored at index pivot_point in str. This pivot_point is chosen by the caller of quicksort(...). I call the function on line 52 -- you won't see this line in the screenshots because it's just I/O -- and pass rand(str.length) for the value of pivot_point, basically telling quicksort(...) to use a random pivot. Note: often, you'll see implementations use different methods to pick out the pivot points, opting for the first or last element, or some other element entirely.

We then declare left = [] and right = [] to hold the values less than the pivot and greater than the pivot, respectively.

In the for loop on line 24 we go through str and put each element in either the left or right arrays, but never both, excluding the pivot, because we don't need to re-sort the pivot; it will be in its final position.

But we're not done yet. We now, on lines 37 and 38, take the newly filled (or not filled) left and right and call quicksort(...) on them, too. Note: this calling of a function from within itself is known as recursion. Make sure you have a terminator (ours is line 10) so that your function doesn't keep calling itself forever.

After the left and right arrays are quickly sorted -- pun intended -- we can stitch them together, the pivot in between, to build the completed, sorted str. We do this on lines 41 and 42, erasing str and then copying left, pivot_char, and right into a newly-emptied str.

On line 44, we flatten str before returning it because pushing left/right to str creates a 2D array, something we do not desire.

C++ Version

Here you'll find the pastebin link; the screenshot is below:

As usual, I chose to use vec in place of str. Other than that, there is only one major contrast from the Ruby version: Before calling quicksort(...), I check if the array-to-sort is empty. This is because of how C++ does random numbers. If I pick a random pivot in for an empty array, passing a random pivot would look like rand() % 0, because the size of an empty array is 0, yet you cannot do a modulo of 0, because you cannot divide by 0.

Conclusion

If you noticed in the title, this article is Part 6.0 that ".0" is there because I am implying the coming of a 6.1 and maybe even 6.2.

Why? Because this method of quicksorting is resource-inefficient. I only showed you it because it's the easiest form of quicksort to understand and implement.

So, stay tuned for Sorting (Part 6.1): Quick Sort [In-Place].

Happy Hacking,
oaktree