Quick Sort In Ruby

Quick Sort oh Quick Sort! Perhaps one of the harder algorithms to get right, and boy was that my experience. The first stumbling block I hit while trying to understand how it works was that there are different implementations of it. Some online resources choose to determine the pivot from the left (array[0]), some from the extreme right (array[array.length – 1]), some randomly sample from the array. Nonetheless, what a truly enjoyable process, so let’s begin.

Quick Sort is an in-place algorithm, means the input array is transformed using no other auxiliary data structure. Said differently, memory is over-written, or the input space is over-written. Another characteristic of Quick Sort is that it’s divide and conquer. It breaks the problem space into smaller and smaller chunks applying the same algorithm at each step to get closer and closer to the solution. Quick Sort is more efficient than Bubble Sort and Insertion sort (for most cases).

Quick sort is the simple process of ordering an array. It’s method involves 3 steps.

  1. Partition the array.
  2. Recurse the left sub-array to sort it
  3. Recurse the right sub array to sort it

Some added terminology, is that of “pivot”. This is a value we choose in the array that would breakdown our array into two parts (partitioning). Part A (or left sub-array) would be those values that are less than the pivot. Part B (or right sub-array) would be those values greater than or equal to the pivot. As an example:

[1, 21, 33, 14, 65, 6, 16 ]

If we selected 16 as our pivot, then the numbers partitioned would look like this:

1, 14, 6 | 16 | 21, 33, 65 # Note values on left smaller, and values on right greater than 16.

With a little more clarity:

irb(main):005:0> test =  [1, 21, 33, 14, 65, 6 ]
=>; [1, 21, 33, 14, 65, 6]
irb(main):006:0> test.partition { |x| x > 16 }
=>; [[1, 14, 6], [21, 33, 65]]

Now if you were paying attention, you would have realised we have just completed step 1, partitioning. The approach I’ve taken is to use the last element as the pivot, though as I said there are different and more efficient strategies online.

Step 2 and 3 are basically recursive calls using partitioning again and again, till there are no more values to partition. If you still struggling with the concept have a look at this absolute gem of a resource where you can literally and visually walk the Quick Sort process. The code will instantly make sense with this, but also you can walk the code through the diagram above.

Rspec:

describe Sorting::QuickSort do
  before :each do
    #@array = [ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 ]
    @array = [ 3, 7, 8, 5, 2, 1, 9, 5, 4 ]
    @qs = Sorting::QuickSort.new
  end

  context 'quick sort' do
    it 'should return an ordered array' do
      expect(@qs.quicksort(@array)).to eq [1, 2, 3, 4, 5, 5, 7, 8, 9]
    end
  end
end

Code:

# Amazing piece of code, tweaked a little
# Thank you - http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Ruby
# 
module Sorting
  class QuickSort
    def quicksort(array)
      return array if array.length <= 1
      pivot = array[array.length - 1]
      left, right = array[0..-2].partition { |x| x < pivot }
      quicksort(left) + [pivot] + quicksort(right)
    end
  end
end

1 comment

  1. I love this algorithm. To me this is the beauty of programming.
    One thing I thought of with regards to the pivot point: would it not be a fraction more efficient selecting index 0 instead of the last element of the array?
    Reason being, selecting the last element means you’d have to looking the length of the array and then perform the lookup, whereas selecting element 0 would skip the “length lookup”

    Not sure how big a difference this would make, but you know I like commenting on your posts, so there you go 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *