# Quicksort in Ruby!

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


Here's my two cents on this.

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

a, b = b, a


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


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}


• 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.

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

• +1, although i do prefer using brackets in method signatures and calls, with one space on each side : example.execute( self ). I find it easier to spot arguments when scanning terse lines of code, and all in all there's many situations where you must use them anyway. That said, it's purely a matter of taste, and sometimes it justs feels more natural not to use brackets. YMMV
– m_x
Apr 29 '13 at 17:13