steps

  1. pick a pivot. (random works well, finding the median is best)
  2. split list into two.
    • items lower than the pivot value go in one list.
    • items greater than the pivot value go in the other list.
  3. recursively apply the above steps to each of the sublists.

The base case for the recursion is an array of size 0 or 1.

class QuickSort
  def sort(items)
    return items if items.size <= 1

    pivot = items[rand(items.size)]
    less, pivots, greater = [], [], []
    items.each do |x|
      if x < pivot
        less << x
      elsif x > pivot
        greater << x
      else
        pivots << x
      end
    end
    sort(less) + pivots + sort(greater)
  end
end

notes

The efficiency of the algorithm relies on finding an appropriate pivot value. The more balanced the two sublists are, the more efficient the divide and conquer will work.

The above example creates a new array for each of the sub lists. An in-place version can be more efficient because it just re-arranges elements in the source list. This reduces the overall memory footprint. Another thing to note is that ruby arrays dynamically expand, so there is no need to specify an array size for each declared array.

One of the key differences between quick sort and merge sort is that quick sort does the sorting as it divides the list into sublists. Merge sort does the sorting during the merge step.

comments powered by Disqus