Concise Quicksort

While preparing for interviews, decided it would be wise to learn how to sort arrays quickly in Ruby, and boy did I find what I was looking for.

If you are a beginner like me, you’ll find this tiny function is dense. The act of unpacking the code was an adventure so educational, I decided to write a post seven times longer than the quicksort method the post is about.

Line 1..2

class Array
 def quicksort

First, we’re editing the Array class. This is called monkey-patching (likely derived from “guerrilla patch” or sneakily changing code). It means we’re extending the original system software locally. And since we’re editing the Array class, the Array methods we use like partition, size, empty, and delete_at apply to the instance of Array we call quicksort on, decluttering our method.

Line 3..4

return [] if empty?
pivot = delete_at(rand(size))

This method is recursive and will stop calling itself when it receives an empty array. The return of the empty array on this line begins the process of returning all values back “up” the stack. Next, we pull one element off our array and assign it to pivot, which we will eventually use to anchor that element’s place in the array, placing all values higher on one side, and lower on the other.

Line 5

left, right = partition(&pivot.method(:>))

Now comes the tricky part: we split the remaining array into two arrays with all the items less than the pivot on the left, and the rest on the right. Before we get to the fancy arguments, let’s breakdown the partition method.

left, right = partition()

Below, you’ll find I built my own version of the partition to better understand how it works.

It walks through an array, swapping any element less than or equal to the pivot with the j value. After each swap, the j value increments, which makes it a bit like a wall separating less-than and greater-than values. Ruby’s partition is fancier and more dynamic than mine, allowing you to pass in any block instead of just the less-than-or-equal-to operator (partition.rb:line 5). Which brings us to the most interesting section of our little quicksort.

&pivot.method(:>)

The method method turns the greater-than (>) method into a lambda. This lets you pass the method around with one of the arguments being the item you called the method on. Let’s say you want to pass the method Math.sqrt around. Simply assign square_root = Math.method(:sqrt) to a function and you can use it as an argument in a method. If you apply the method method on an expression like 0.method(:>), it will also include the 0 as the first argument in the method.

negative = 0.method(:>)
=> #<Method: Fixnum#>>

negative.call(-5)
=> true

negative.call(3)
=> false

The & syntax turns the lambda into a block. Using our square_root variable in the example above, we can apply the lambda to an array like so:

[9, 16, 25].map(&square_root)
=> [3.0, 4.0, 5.0]

Line 6

return *left.quicksort, pivot, *right.quicksort

The splat operator (*) deconstructs all the arrays as they unpack back up the recursed stack, like the.flatten method. If you do not use a splat operator, your solution will look like this:

[3, 1, 2].quicksort_without_splat_return
=> [[[[], 1, []], 2, []], 3, []]

The brackets were included in the return because when the recursed function begins to wind back up the stack, the balanced, nested array is split by the integer pivot return values.

[[[[], 1, []], 2, []], 3, []] == [1, 2, 3]
=> false

The splat operator deconstructs the empty brackets as they are returned.

[*[*[*[], 1, *[]], 2, *[]], 3, *[]] == [1, 2, 3]
=> true

And that is a breakdown of the coolest quicksort method I have found yet.

Like what you read? Give Adames H. a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.