Quick sort is the one of the most popular sorting algorithms to implement, and it is also considered the most efficient in many cases. The visual below shows you the high-level view of quick sort.

Explanation of Quicksort

In this example, the algorithm chooses a pivot value, which in this case is 4. From there it splits the collection into two groups - one with the elements to the left of 4 and the other to the right of 4. Next, quicksort is recursively called on the newly formed left and right collections. For example, the group lower than 4 is chosen next and another pivot point for this subgroup is identified. Based on this pivot point, the array is sorted again. Likewise, the larger group goes through two smaller subgroups, and eventually all the values are merged together to create a sorted list.

Quicksort Code Example

Clear as mud? Don't worry if the concept is still a bit fuzzy, Quicksort isn't the most intuitive algorithm if you've never worked with it before. Let's dive into the code example, because even though Quicksort is quite complex, it actually has a relatively straightforward code implementation if you leverage the right built in Ruby methods. We'll start by opening up the array class and we'll add a new method to Array called quicksort. An advantage to this metaprogramming approach is that we don't have to pass an argument to the method like we had to for our bubble sort guide. With this approach we can directly call the method on any array.

class Array
  def quicksort
  end
end

Next let's check if the array that calls this method is empty, and if so, then return an empty array. This is required for both error handling and so that the quicksort method will know when to end.

def quicksort
  return [] if empty?
end

Next, we have to pick our pivot element. Let's say our array is [34, 2, 1, 5, 3], we're going to select a random value as the pivot. To choose this value, implement the following code:

pivot = delete_at(rand(size))

Essentially, this code picks a random index number from the array's length, and passes that random index number to the array to pull out the element at that random index number. This value is stored in a variable called pivot.

devCamp Note: By opening up the Array class we are able to call the size method without passing it to a specific array because we opened up the Array class and self is assumed. If you tried calling this line of code outside of the Array class definition it would throw an error.

Next, we are going to partition the array based on the pivot variable, and to do this, we are going to use the partition method. This method splits a collection in half. It takes a block as an argument and inside of the block we're going to use the ampersand syntax to let the program know that it needs to split array into two components. One that will be less than the pivot value, and one that will be greater than the pivot. And it will store these two collections in variables named left and right.

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

Finally, return the left array, pivot and right array and recursively call quicksort on both of the returned arrays. We're also using the splat argument represented by * before each collection.

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

For our example let's assume our pivot is 1. The, the array gets broken down into two parts, and each of these collections will be sorted again using the same method call.

The entire code looks like this:

class Array
  def quicksort
    return [] if empty?

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

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

Now let's add the code to test this out:

arr = [34, 2, 1, 5, 3]
p arr.quicksort

The output is:

[1, 2, 3, 5, 34]

Which means that everything works properly. This is one of the shortest implementations of quicksort that I've ever seen. Many other languages have Quick sort implementations that would take up hundreds of lines of code, however by leveraging some built in Ruby methods such as partition we're able to consolidate the program and make it easier to read.