[Courses] [Ruby] Lesson 0: Homework

[Laurel Fan]

On 11/14/05, Anne G <anne at wjh.harvard.edu> wrote:
Hi Anne!

Great example implementation of quicksort.  It shows off one of the
unique features of ruby, which is the block syntax (the { |i| i < m }
stuff).  There's more about blocks in the book, and this interview
with the language designer (Yukihiro "Matz" Matsumoto) gives a little
more background:

http://www.artima.com/intv/closures.html

> def quicksort( xs )
>    puts "Iterations, array size = "
>    puts xs.size
>    puts "Print the array"
>    puts xs
>    return xs if xs.size <= 1
>    m = xs[0] # Split-Element
>    quicksort(xs.select { |i| i < m } ) +
>      xs.select { |i| i == m } +
>      quicksort(xs.select { |i| i > m } )
> end
> puts "Final array"
> puts quicksort([13, 11, 74, 69, 0])
> puts "hello we are done"
>
> Here is the comment
> -----------------------------------------------------------------
> line by line:
>
>   return xs if xs.size <= 1
>
>
> If the size is 1 or 0, we just return the array; it's already sorted
>
>   m = xs[0]
>
> Here we choose an arbitrary "Pivot" element.
> This can be any element of the array. In this case we choose
> the first.
>
>   quicksort(xs.select { |i| i < m } ) +
>      xs.select { |i| i == m } +
>      quicksort(xs.select{ |i| i > m } )
>
> This is a little more complicated. First, let's figure out
> what those selects do. The first one selects all elements
> less than the pivot. The second selects all elements equal
> to the pivot. The final one selects all elements greater
> than the pivot. Let's modify this and use some temp variables.
>
>   less = xs.select { |i| i < m }
>   equal = xs.select { |i| i == m }
>   more = xs.select { |i| i > m }
>
>   quicksort( less ) +
>     equal +
>     quicksort( more ) )
>
>
> In other words, we're returning a list of all the elements
> less than the pivot, sorted, then all those equal, then all
> those greater, sorted. This is classic divide-and-conquer
> recursion. Quicksort is applied to ever smaller lists until
> we use it on lists of one or zero elements, and we hit the
> terminating condition.
>
> -----------------------------------------------------------
> the xs.select is equivalent to the find function in matlab.
>
> xs.select { |i| i < m }
> |i| must mean for each element of xs compare it to m
> what is confustin to me is I usually use i as an index, but
> since m=xs[0], i must be an array element.

Yes, you're right.  If you use matlab, you might like all the
functions on Enumerable (like select), since they kind of resemble
doing vector operations.

> -----------------------------------------------------------
> I have never used recursion like this, it is very efficient,
> but I wonder about readability!

Sometimes I find it more readable to use the long form, such as:

xs.select do |i|
  i < m
end

In any case, I think it takes some getting used to.  It's not as
immediately intuitive as some concepts (like if/else).  I think there
are lots of cases when it's more readable than doing it without it. 
When you do a sort in C, and want to define your own comparison
function, you have to define a function separately and make a function
pointer;  in other OO languages like C++ and Java, the same thing
might require making a completely different object.



--
Laurel Fan
http://dreadnought.gorgorg.org