From: Gary Wright <gwtmp01@...>
Date: 2007-02-10T10:09:46+09:00
Subject: Re: Your favorite bit of ruby code?


On Feb 8, 2007, at 3:49 PM, Carl Lerche wrote:
> I'm just curious what your favorite bit of ruby code is? Do you have
> any small bits, methods, classes, or anything else, that just make you
> say "Wow, that is sweet!"

I can't remember where I first saw this bit of code but I was able to
google and find a ruby-talk posting by Wayne Vucenic with:

def quicksort(a)
   return a if a.size <= 1
   pivot = a[0]
   quicksort(a.select {|i| i < pivot }) +
             a.select {|i| i == pivot } +
   quicksort(a.select {|i| i > pivot })
end

I realize that Ruby has a built in sort but I was absolutely stunned
at how well the quicksort algorithm could be coded in Ruby with
little if any extraneous syntax.

Here is another version that might even be 'better' (via Gabriele Renzi)

def qs(a)
    return a if a.size <=1
    pivot = a.shift
    less, more = a.partition{|y| y < pivot}
    qs(less) + [pivot] + qs(more)
end

In ruby 1.9, splat is a little more flexible, which gives:

def qs(a)
    return a if a.size <=1
    pivot = a.shift
    less, more = a.partition{|y| y < pivot}
    [*qs(less), pivot, *qs(more)]             # only works in 1.9
end

And if you want to use the nice open class features of Ruby:

class Array
   def qs
     return self if size <=1
     pivot = shift
     less, more = partition{ |y| y < pivot }
     [*less.qs, pivot, *more.qs]
   end
end

Gary Wright