クイックソート

Question

###前提・実現したいこと
ここに質問したいことを詳細に書いてください
『アルゴリズムを、はじめよう」という書籍を参考に、Rubyでクイックソートのプログラムを書いています。この書籍にはプログラミング言語による模範解答は載せられていないため、プログラムを自分で書く必要があります。
###発生している問題・エラーメッセージ
下記のコードを試した結果、おそらくですが、無限ループに陥ってしまいました。

エラーメッセージ

###該当のソースコード
Ruby
ここにご自身が実行したソースコードを書いてください
def quick_sort(array, left, right)
i = left + 1
k = right

while i < k
while array[i] < array[left] && i < right
i = i + 1
end

while array[i] >= array[left] && k > left
  k = k + 1
end

if i < k
  w = array[left]
  array[left] = array[k]
  array[k] = w
end

end

if left < k - 1
quick_sort(array, left, k - 1)
end

if k + 1 < right
quick_sort(array, k + 1, right)
end

end

array = [5, 4, 7, 6, 8, 3, 1, 2, 9]
quick_sort(array, 0, 8)

puts array

###試したこと
課題に対してアプローチしたことを記載してください
エラーメッセージが出ていた頃は、ひたすらそのエラーを潰していましたが、無限ループになってからは、エラーの原因がわかりません。webページも参考にしましたが、自分が書いたコードは動いてくれませんでした…。

###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報
よろしくお願い致します。

Answer 1

... 無限ループになってからは、エラーの原因がわかりません。..

問題を解決するには、まずどこがループしているかを見つけることが必要です。
ソートする配列を単純なものから始めて、だんだんに複雑なものにしていって、動作を確認すると良いです。

質問文にあったコードは、配列のサイズが 1 のときは動作しました。
サイズが2になるとい無限ループしました。
どこでループしているかがわかるように puts を追加してみています。

def quick_sort(array, left, right)
  puts "quick_sort(left:#{left}, right:#{right})"
  i = left + 1
  k = right

  puts 1
  while i < k
    puts 1.1
    while array[i] < array[left] && i < right
      i += 1
    end

    puts 1.2
    while array[i] >= array[left] && k > left
      k += 1
    end

    puts 1.3
    if i < k
      w = array[left]
      array[left] = array[k]
      array[k] = w
    end
  end

  puts 2
  if left < k - 1
    quick_sort(array, left, k - 1)
  end

  if k + 1 < right
    quick_sort(array, k + 1, right)
  end
end

# array = [5, 4, 7, 6, 8, 3, 1, 2, 9]
# array = [1]
array = [1, 2]
# array = [2, 1]
quick_sort(array, 0, array.size)

puts array

デバッガの使い方を覚えれば、puts 追加しなくても挙動を追うことができるようになります。
(ruby デバッグ などで google 検索してみてください)

プログラムが動作するように修正できたら、ぜひそれをここに投稿してください。
次は、プログラムの改善点などについてのコメントがもらえると思います。

Comments

[GenkiNishiyama]

ありがとうございました！
katoyさんのヒントをもとに動作するプログラムを書くことができました！
初めての質問でしたが、自分でウンウン悩んでいたら、もっと時間がかかっていたと思います。
ありがとうございました！

以下、コードです。

def quick_sort(array, left, right)
i = left + 1
k = right

while i < k
puts "B"
while array[i] < array[left] && i < right
i = i + 1
end

while array[k] >= array[left] && k > left
k = k - 1
end

if i < k
w = array[i]
array[i] = array[k]
array[k] = w
end
end

if array[left] > array[k]
w = array[left]
array[left] = array[k]
array[k] = w
end

if left < k - 1
quick_sort(array, left, k - 1)
end

if k + 1 < right
quick_sort(array, k + 1, right)
end
end

array = [5, 4, 7, 6, 8, 3, 1, 2, 9]
quick_sort(array, 0, array.size - 1)

puts array

[katoy]

ruby quicksort で検索すると、たくさんコード例を見つけることができます。
例えば
Rubyでクイックソート [http://qiita.com/7kaji/items/5518479579bc36359bc8]
などのコードとくらべてみると、よい勉強になるとおもいます。

参考として↓に ↑のコメントのコードを書き換えてものを記載します。
これは、 quick_sort() の中身を動作をかえずに短くし、
さらに配列の数が 7個, 8個 で値に重複がない場合にソートが正常動作していること
の確認をするようにしています。

def quick_sort(array, left, right)
i = left + 1
k = right

while i < k
i += 1 while array[i] < array[left] && i < right
k -= 1 while array[k] >= array[left] && k > left
array[i], array[k] = array[k], array[i] if i < k
end
array[left], array[k] = array[k], array[left] if array[left] > array[k]

quick_sort(array, left, k - 1) if left < k - 1
quick_sort(array, k + 1, right) if k + 1 < right
end

array = [5, 4, 7, 6, 8, 3, 1, 2, 9]
quick_sort(array, 0, array.size - 1)
puts array.join(', ')

[1, 2, 3, 4, 5, 6, 7].permutation(7) do |ar|
quick_sort(ar, 0, ar.size - 1)
fail "Can not sort #{ar.join}" if ar.join != '1234567'
end

[1, 2, 3, 4, 5, 6, 7, 8].permutation(8) do |ar|
quick_sort(ar, 0, ar.size - 1)
fail "Can not sort #{ar.join}" if ar.join != '12345678'
end