I am new to Ruby and just started picking up the language a couple of days ago. As an exercise, I tried to implement simple quicksort
class Sort
def swap(i,j)
@data[i], @data[j] = @data[j], @data[i]
end
def quicksort(lower=0, upper = @data.length - 1)
return nil if lower >= upper
m = lower
i = 0
((lower+1)..upper).each do |i|
swap(++m, i) if @data[i] < @data[lower]
end
swap(m, lower)
quicksort1(lower, m -1)
quicksort1(m+1, upper)
end
end
Calling quicksort on 10,000 integers gives me a stack level error. After googling, I realized that tail recursion is not yet supported in Ruby ( view ). But then I found the following snippet (from here )
def qs(v)
return v if v.nil? or v.length <= 1
less, more = v[1..-1].partition { |i| i < v[0] }
qs(less) + [v[0]] + qs(more)
end
Running the second fragment works fine even with a million integers. However, as far as I can tell, there is tail recursion at the end. So what I do not understand here?
source
share