CODEWITHSUNDEEP
ruby
alexZ
alexZ

Reputation: 189

ruby quicksort error

below is my quicksort implementation in ruby(using the first element as pivot). But there's an error I cannot figure out why

def quicksort(items)
   return items if items.nil? or items.length <= 1

   first=items[0]

   left,right=parti(items,0,items.length)

   quicksort(left) + [first] + quicksort(right)

end

def parti(s,l,r)
  p=s[l]
  i=l+1
  (l+1..r).each do |x|
      if s[x] < p
          s[x],s[i] = s[i],s[x]
          i+=1
      end
  end
  s[l],s[i-1] = s[i-1],s[l]
  return [s[0..i-2],s[i..r]]
end

The error:

putarray.rb:38:in `block in parti': undefined method `<' for nil:NilClass (NoM
hodError)
      from inputarray.rb:37:in `each'
      from inputarray.rb:37:in `parti'
      from inputarray.rb:22:in `quicksort'
      from inputarray.rb:47:in `<main>'

it says in

 if s[x] < p

s[x] is NilClass.

UPDATE: It turns out 

left,right=parti(items,0,items.length) should be 
left,right=parti(items,0,items.length-1)

But after this change, an error

inputarray.rb:37: stack level too deep (SystemStackError)

point to 

(l+1..r).each do |x|

Didn't find any good explanation on the internet.

Upvotes: 0

Views: 119

Answers (1)

Jason Kim
Jason Kim

Reputation: 19031

Keep in mind that in Ruby, array index starts from 0, not 1.

Therefore items.length will return the value of 1 greater than the maximum index in the array.

Try right=parti(items,0,items.length-1) instead of right=parti(items,0,items.length).

Upvotes: 1

Related Questions