Hello 0x00sec!
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
#! /usr/bin/env ruby
# str is array of chars
# pivot point is index in array to pivot on
# returns type like `str`
def quicksort(str, pivot_point)
strlen = str.length
# recursion terminating condition:
return str if strlen <= 1
# find the pivot character
pivot_char = str[pivot_point]
# make new arrays for left and right of pivot
# note: I'm very much aware that this is not the most efficient method,
# but it WILL make it easier to understand the concept of quicksort before
# I proceed to cover the in-place version
left = []
right = []
# go through all the elements, put the ones smaller than pivot_char on the left;
# ...bigger on the right.
for i in 0...strlen # exclusive range: 0 to one less than str's length
next if i == pivot_point # skip over the pivot, we don't want to put it anywhere
# because it'll already be in final position at the end of the function.
if str[i] < pivot_char
left << str[i]
else
right << str[i]
end
end
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(...). 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.
# utilize recursion to sort the left and right arrays, until the partitions become
# a singular-element array or an empty one.
left = quicksort(left, rand(left.length))
right = quicksort(right, rand(right.length))
# overwrite the original str and drop the new stuff in, in order
str = []
str << left << pivot_char << right
return str.flatten # flatten because we pushed an array, a character/one-letter-string, and another array
# FYI: flatten makes a 2+D array 1D.
end
puts "give me a string"
str = gets.chomp.split('')
puts quicksort(str, rand(str.length)).join('')
But we’re not done yet. We now 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 by erasing str and then copying left, pivot_char, and right into the just-emptied str.
We flatten str before returning it because pushing left/right to str creates a 2D array, something we do not desire.
C++ Version
void quicksort(vector<char>& vec, const int pivot_point) {
if (vec.size() <= 1) return;
char pivot_char = vec[pivot_point];
vector<char> left, right;
for (int i = 0, n = vec.size(); i < n; i++) {
if (i == pivot_point) continue;
if (vec[i] < pivot_char) {
left.push_back(vec[i]);
} else {
right.push_back(vec[i]);
}
}
if (!left.empty()) quicksort(left, rand() % left.size());
if (!right.empty()) quicksort(right, rand() % right.size());
vec = left;
vec.push_back(pivot_char);
vec.insert(vec.end(), right.begin(), right.end());
}
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