-2

選択ソートを書いていますが、配列を渡すだけで機能しますが、再帰を使用しようとすると、スタックが深すぎるというエラーが発生します。私はこれで何が間違っていますか？

def selectionSortRecursive(array, arrayPosition)
   if arrayPosition == (array.length-1)
      puts "End of the line folks!"
      return array
   end   
   while arrayPosition >= 1 && array[arrayPosition] < array[arrayPosition - 1] do 
    puts "This is pass #{arrayPosition}"
    if array[arrayPosition] < array[arrayPosition - 1]
      tmp = array[arrayPosition]
      array[arrayPosition] = array[arrayPosition - 1]
      array[arrayPosition - 1] = tmp
    end # end if
    arrayPosition += 1
  end
  selectionSortRecursive(array, arrayPosition)
  return array
end

これは私がそれをテストするために使用しているものです:

selectionSortRecursive(array, 1)
4

1 に答える 1

0

そのような状況では、どのコードがどの値で実行されるかを確認するために、print ステートメントを入れるだけです。あなたは見たでしょう：

$ ruby -w t4.rb 
t4.rb:21: warning: mismatched indentations at 'end' with 'while' at 10
initial array=[4, 3, 2, 1], initial position=2
last_pos=3
This is pass 2 cur=2  pre=3
after switching elements : [4, 2, 3, 1]
This is pass 3 cur=1  pre=3
after switching elements : [4, 2, 1, 3]
initial array=[4, 2, 1, 3], initial position=4
last_pos=3
initial array=[4, 2, 1, 3], initial position=4
last_pos=3
initial array=[4, 2, 1, 3], initial position=4
last_pos=3
initial array=[4, 2, 1, 3], initial position=4
last_pos=3
.......
t4.rb:2: stack level too deep (SystemStackError)

再帰を停止するには、いくつかの条件を確認する必要があります。再帰を説明するために常に使用される何百万もの階乗またはフィボナッチの例を見てください。

どのように並べ替えたいのかわかりませんが、このコードは機能します:

def selectionSortRecursive(array, arrayPosition)
   puts "initial array=#{array}, initial position=#{arrayPosition}"
   initial_array_position = arrayPosition
   last_pos = array.length - 1
   puts "last_pos=#{last_pos}"
   if arrayPosition == (last_pos)
      puts "End of the line folks!"
      return array
   end   
   while arrayPosition >= 1 && arrayPosition <= last_pos && array[arrayPosition] < array[arrayPosition - 1] do
    cur = array[arrayPosition]
    pre = array[arrayPosition - 1]
    puts "This is pass #{arrayPosition} cur=#{cur}  pre=#{pre}"
    if array[arrayPosition] < array[arrayPosition - 1]
      tmp = array[arrayPosition]
      array[arrayPosition] = array[arrayPosition - 1]
      array[arrayPosition - 1] = tmp
      puts "after switching elements : #{array}"
    end # end if
    arrayPosition += 1
   end
   selectionSortRecursive(array, arrayPosition) if arrayPosition != initial_array_position
   return array
end

p selectionSortRecursive([4,3,2,1], 2)

実行:

$ ruby -w t4.rb 
initial array=[4, 3, 2, 1], initial position=2
last_pos=3
This is pass 2 cur=2  pre=3
after switching elements : [4, 2, 3, 1]
This is pass 3 cur=1  pre=3
after switching elements : [4, 2, 1, 3]
initial array=[4, 2, 1, 3], initial position=4
last_pos=3
[4, 2, 1, 3]
于 2013-01-25T17:39:27.487 に答える