CODEWITHSUNDEEP
ruby
lkahtz
lkahtz

Reputation: 4796

Stack level too deep error in ruby's recursive call

I am trying to implement the quick sort algorithm using ruby. See what I did:

class Array

  def quick_sort  #line 14
    less=[];greater=[]
    if self.length<=1
      self[0]
    else
      i=1
      while i<self.length
        if self[i]<=self[0]
          less << self[i]
        else
          greater << self[i]
        end
      i=i+1
      end
    end
    less.quick_sort + self[0] + greater.quick_sort #line 29
  end
end
[1,3,2,5,4].quick_sort #line 32

This generated the error:

bubble_sort.rb:29:in `quick_sort': stack level too deep (SystemStackError)
    from bubble_sort.rb:29:in `quick_sort'
    from bubble_sort.rb:32

Why is this happening?

Upvotes: 2

Views: 6756

Answers (3)

James Kyburz
James Kyburz

Reputation: 14453

I think the problem in your example was you needed an explicit return.

if self.length<=1
  self[0]

should have been

return [] if self == []

and

less.quick_sort + self[0] + greater.quick_sort #line 29

should have been 

less.quick_sort + [self[0]] + greater.quick_sort #line 29

Here is a working example

class Array

  def quick_sort
    return [] if self == []
    pivotal = self.shift;
    less, greater = [], []
    self.each do |x|
      if x <= pivotal 
        less << x
      else 
        greater << x
      end
    end
    return less.quick_sort + [pivotal] + greater.quick_sort
  end
end
[1,3,2,5,4].quick_sort # => [1, 2, 3, 4, 5]

Upvotes: 3

Achim
Achim

Reputation: 15712

In that part you should not handle the "=" case. Only < and > should be handled. Therefore your algorithm never stops and causes an infinite recursion.

if self[i]<=self[0]
  less << self[i]
else
  greater << self[i]
end

Upvotes: 1

sepp2k
sepp2k

Reputation: 370212

less.quick_sort + self[0] + greater.quick_sort

This line is outside of the if statement, so it gets executed whether self.length<=1 is true or not. Consequently the method recurses infinitely, which causes the stack to overflow.

It should also be pointed out that self[0] does not return an array (unless self is an array of arrays), so it does not make sense to use Array#+ on it. Nor does it make sense as a return value for your quick_sort method.

Upvotes: 1

Related Questions