0

以下は、ルビーでのクイックソートの実装です(最初の要素をピボットとして使用)。しかし、理由がわからないエラーがあります

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

エラー:

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>'

それは言う

 if s[x] < p

s[x] は NilClass です。

更新:判明

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

しかし、この変更後、エラー

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

指し示す

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

インターネット上で適切な説明が見つかりませんでした。

4

1 に答える 1

1

Ruby では、配列のインデックスは 1 ではなく 0 から始まることに注意してください。

したがってitems.length、配列内の最大インデックスよりも 1 大きい値が返されます。

right=parti(items,0,items.length-1)の代わりに試してくださいright=parti(items,0,items.length)

于 2012-06-28T21:30:03.570 に答える