Friday, February 22, 2013

Partition and Splat in Quick Sort

The Ruby Array has a partition method that takes a block and returns an array of elements for which the block evaluates to true, and a second array of elements for which the block evaluates to false.

This method can be used in a quick sort, which involves selecting one element to be a pivot and putting all other elements into either a "less than" array or "greater than" array and sorting each other those the same way.

This is a recursive sort, which means it calls itself.

def quick_sort number_array
  return number_array unless number_array.size > 1
  pivot, *the_rest = number_array
  less, more = the_rest.partition { |number| number < pivot }
  quick_sort(less) + [pivot] + quick_sort(more)

this_array = [22,66,4,44,5,7,6,8,77,33,8,99,6]

puts "unsorted: #{this_array.inspect}"

puts "sorted: #{quick_sort(this_array).inspect}"

Also interesting is the splat operator (the asterisk), which enables the new variable to take more than one parameter.  When an array is assigned to multiple variables, the splat operator allows an item to take enough elements to make the assignment work.  Above it is assigning one element to be the pivot and the rest to be partitioned.

When defining a method, the splat operator can be used with one of the parameters, enabling it to accept multiple parameters as an array.  Although it can be anywhere in the parameter list, using splat on the final parameter is preferred because extra parameters will all go into the array instead of changing how other parameters are assigned.

As used above, elements are used arbitrarily so the order doesn't matter as long as the_rest gets all but the element assigned to pivot.  I guess you could think of the left side of the assignment as the method definition's parameter list and the right as a call to that method.