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

(oaktree) #1

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` 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

1 Like

Sorting (Part 7.0): Merge Sort
#2

Nicely written code, or in other words “beautiful code”.

0 Likes

(oaktree) closed #3

This topic was automatically closed after 30 days. New replies are no longer allowed.

0 Likes