Quicksort in Ruby

One of the fastest sorting algorithms is quicksort. To sort a list of items via quicksort:

(1) Pick a random element from the list; this is the pivot.

(2) Go through each of the other elements of the list. For each element, if it’s smaller than the pivot, it goes into a new “left array” to the left of the pivot; if it’s larger than the pivot, it goes into a new “right array” to the right of the pivot.

(3) After that, if the new arrays each contain only one element, you’re basically done: the sorted list consists of the left array + pivot + right array.

(3) If the new arrays each contain more than one element, recursively perform steps 1-3 on the new arrays.

Essentially, a quicksort involves breaking the array into smaller and smaller pieces, and then sorting each of these smaller pieces until you work your way up to a complete sorted array.

Which element should you use as the pivot in order to perform quicksort the fastest? It depends. If you choose the first element of the array as the pivot, and the array is sorted in reverse order, you’re in the worst-case scenario, because every single element will go into an array to the left of the pivot, and you’ll have to perform the recursive function n times, where n is the number of elements in the array. In this worst-case scenario, checking n elements n times gives a runtime of n * n, or O(n2) – very slow.

It turns out the best way to even out the extremes is to pick a random pivot. This gives you an average-case runtime of O(n log n). Why? Because you’re checking each element of the array, but in each round on average, you’re cutting the length of the left and right arrays in half. If the array has 8 elements, it will take 3 rounds to get down to sub-arrays of 1 element each: starting from 8, you go to 4, then 2, then 1. That’s log2 8, or log n. So you’re checking n element of the array and you’re doing it log n times, or n * log n, for a runtime of O(n log n).

I decided to try implementing quicksort via Ruby. Here’s my program:

def quicksort(array)
  return array if array.length < 2
  pivot = array.delete_at(rand(array.length))
  left_array = []
  right_array = []
  array.each do |item|
    if item < pivot
      left_array << item
    else
      right_array << item
    end
  end
  return quicksort(left_array) + [pivot] + quicksort(right_array)
end

That's quicksort.

Leave a Reply

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