[Courses] [Ruby] Lesson 0: Homework

[Anne G]

The course web site is back, yeah.

I figured out how to run ruby with rubycocoa. I just add a
ruby file, erase the lines about a class, and enter the ruby
code. It compiles, and prints in the run log window.

Here is my homework. I cheated and found a snipet of
text which makes sense to me, and also has a commentary
http://redhanded.hobix.com/inspect/thinStrandOfSearchAndReplaceRails.html
the snipet was taken from somewhere else, and I added print
to see what it does.

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.

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

Thank you so much for this course. Finding this little
snipet and running it was fun. And it was interesting to see
what others have found

Anne