Quicksort in Ruby!

Question

I've been teaching myself Ruby this weekend. First of all, I am aware that there is a built-in sort function. I've written this code strictly as an exercise.

I have background primarily in C# and Javascript, so this is a change of pace for me.

If you are a seasoned professional with a lot of Ruby experience, my code will probably make your hair stand on end, so please advise me how to do this the right way in case I'm ever sitting next to you writing Ruby code.

The code appears to work, but I'll bet that the convention that I'm used to using is not the best way to get things done in Ruby.

class Array
  @@swap = lambda {|a, i0, i1|
    x = a[i0]
    a[i0] = a[i1]
    a[i1] = x
    # puts "Swapping elements at position #{i0} and #{i1}"
    # puts a.inspect()
  }
  @@recurse = lambda {|a, iStart, iEnd|
    # puts "iStart = #{iStart}, iEnd = #{iEnd}, a=#{a.inspect()}"
    # base case
    return if (iStart == iEnd)
    pivot = a[iEnd]
    i = iStart # iterator to count over the array
    j = iStart # the index of the last element less than the pivot
    while i < iEnd
      if a[i] < pivot
        @@swap.call(a, i, j)
        j += 1
      end #if
      i += 1
    end #while
    # Put the pivot element after the last element less than the pivot element
    @@swap.call(a, j, iEnd)
    # Recurse over the elements less than the pivot and the elements greater than the pivot
    thread0 = Thread.new() { @@recurse.call(a, iStart, j - 1) if j != iStart }
    .join()
    thread1 = Thread.new() { @@recurse.call(a, j + 1, iEnd)   if j != iEnd }
    .join()
  }
  def quickSort()
    @@recurse.call(self, 0, self.length() - 1)
  end #quickSort
end

a = []
i = 0
until i === 1000
   a.push(i)
   i += 1
end

a.shuffle()
a.quickSort()

errorFound = false
i = 0
until i === 1000
  errorFound = true unless (i === a[i])
  i += 1
end
puts 'All sorted' unless errorFound
puts 'Error' if errorFound

Answer 1

Here's my two cents on this.

• For starters, swapping two elements can be expressed in ruby this way :

  a, b = b, a
  

• Instead of :

  a = []
  i = 0
  until i === 1000
    a.push(i)
    i += 1
  end 
  

  use a range and cast it into an array:

  a = (0..1000).to_a
  

• Instead of :

  errorFound = false
  i = 0
  until i === 1000
    errorFound = true unless (i === a[i])
    i += 1
  end
  

  do this :

  error_found = a.each_with_index.any? {|value, index| value != index}
  

• Be aware that threads in ruby aren't always 'real' threads

• The use of class variables is somewhat shuned by ruby developpers because these variables are shared between the class and its descendants, which leads to nasty bugs when you are not aware of this property. Class-level instance variables are preferred, and some have implemented mechanisms for "real", inheritable class variables

• In general, learn by heart all methods from the Enumerable Module. These are really handy and expressive, and any class just needs to implement an each method to fully benefit from its iterative goodness... In the end, ruby devs tend to prefer iterators over loops, except for some special cases (in place modification messing with indexes, etc.).

• Use blocks / procs / lambdas. Blocks are just plain awesome and any idiomatic ruby script is bound to be riddled with them. Coding with closures / anonymous functions can be hard to grasp at first, but it's really rewarding. That said, I don't really get why you want to use procs in this case (i.e. for "recurse"). A class ("static") method would be suitable here.

Answer 2

What m_x said, plus Some stylistic suggestions:

For long blocks (like your lamba initialisations) do ... end are usually preferred for readability to curly braces (though some would beg to differ).

Comments documenting methods are usually put before the method (makes auto-documentation tools happy)

It's arguably preferable to just define method functionality inside a method definition instead of a separate object (i.e. a lambda). If you want to define the instance specific version of the method in terms of the general version, you can do something like:

class Array
  def self.quicksort a, iStart=0, iEnd=nil
    iEnd ||= a.length-1
    ...
  end

  def quicksort
    self.class.quicksort self
  end
end

Also

i = iStart
while i < iEnd
  ...
  i += 1
end

can be:

iStart.upto(iEnd-1) do |i|
  ...
end

or:

(iStart...iEnd).each do |i|
  ...
end

Unnecessary brackets in method calls are unnecessary (and bad feng shui).

Finally it is acceptable and arguably neater when attaching a short method call to the tail of a block to keep it on the same line i.e. thread = Thread.new {...}.join. This can improve readability a lot in some instances: read_books = book_shelf.each_book.map { |book| book.read if book.cover.is_pretty? }.compact