質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.06%

クイックソート

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 1,420

score 13

前提・実現したいこと

ここに質問したいことを詳細に書いてください
『アルゴリズムを、はじめよう」という書籍を参考に、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/ツール等のバージョンなど)

より詳細な情報
よろしくお願い致します。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+3

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

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

質問文にあったコードは、配列のサイズが 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 検索してみてください)

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/05/01 13:13

    ありがとうございました!
    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

    キャンセル

  • 2016/05/01 14:59

    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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.06%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る