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

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

ただいまの
回答率

90.61%

  • Ruby

    7317questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • アルゴリズム

    392questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • ソート

    63questions

    複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

  • ループ

    49questions

    ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

ruby にてクイックソートのプログラムを作成しています。なぜか無限ループに陥ってしまいました。

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 996

shocyu

score 10

ruby を用いて様々なアルゴリズムのプログラムを作成しています。趣味の範囲ではありますが、これからより複雑なアルゴリズムを記述すべく基礎的なものから製作しています。

「プログラミングの宝箱-アルゴリズムとデータ構造」(紀平拓男、春日伸弥、Softbank Creative, 2011) を参考にしてソースを書いています。こちらは基本C言語でソースが書かれていますが、それを ruby に移植しようと考えています。

ですが、どの並びの配列においても、うまく配列の値の交換がされずに、値が思うように変化せず、最後には無限ループに陥ってしまいました。きわどい並びの配列の処理で躓いているのかもしれません。

ソースをご覧いただき、直すべき点がございましたら、ご指摘をお願いいたします。

なお ruby の Array くらすの sort メソッドは基本クイックソートで書かれているそうです。ですので、このプログラム以降、計算回数が少なく安定しているマージソートを自分のモジュールに付け加える予定です。

よろしくお願いします。ソースは以下になります。
# Sort モジュール(クイックソートとマージソートの処理で構成)
module Sort

# quick_sort メソッド
def self.quick_sort(bottom, top, data)

  lower = bottom
  upper = top

  temp = 0.0
  div = 0.0

  #先頭の値を「適当な値 = div」とする(配列のいちばん最初の成分の値)
  div = data[bottom]

  #puts "data1 = " +div.to_s

  #puts "lower = " + lower.to_s + ", upper = " + upper.to_s

  # lower(下から上がっていく値)と upper (上から下がっていく値)が交わるまで繰り返し
  while lower < upper do

    while (lower < upper) && (data[lower] < div) do
      lower += 1
      puts "lower = " + lower.to_s

      if lower == upper
        break
      end
    end

    while (lower < upper) && (data[upper] > div) do
      upper -= 1
      puts "upper =" + upper.to_s

      if upper == lower
        break
      end
    end

    if lower < upper
      temp = data[lower]
      data[lower] = data[upper]
      data[upper] = temp
    else
      break
    end

    p data
    lower = bottom
    upper = top

  end

  # 最初に選択した値 (data[bottom] ) を中央(lower = upper の位置)に移動する
  temp = data[bottom]
  data[bottom] = data[upper]
  data[upper] = temp
  p data

  # 真ん中に来た値の前半と後半で再びソート(再帰的処理)
  #(例外処理)upper(真ん中の地点)が bottom かその1つ上の場合 -> 後半だけ再びソート
  if upper <= bottom + 1
    self.quick_sort( (upper + 1), top, data)
  #(例外処理)upper が top かその1つ下の場合 -> 前半だけ再びソート
  elsif upper >= top -1
    self.quick_sort( bottom, (upper - 1), data)
  #(それ以外)前半、後半とも再びソート
  else
    self.quick_sort(bottom, (upper - 1), data)
    self.quick_sort( (upper + 1), top, data)
  end

end
# quick_sort メソッド終わり

end
#Sort モジュール終わり

#配列を生成し、ソートする(main 処理)

#配列の大きさを入力
puts "Number of index"
a = gets.to_i
N = a

# 要素数Nの配列を生成
sort_array = Array.new(N)

puts "Before sort"
# 1000以下の乱数を生成し、sort_array配列に格納
for i in 0..(N - 1) do

  sort_array[i] = Random.rand(1000)
  print sort_array[i].to_s + ", "
end

puts "\n"

puts "Sort is started"
# quick_sort メソッド呼び出し
Sort.quick_sort(0, (N - 1), sort_array)

puts "Sort ended"
for i in 0..(N -1) do
  print sort_array[i].to_s + ", "
end

puts "\n"
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 1

checkベストアンサー

+1

まずここ
  # 最初に選択した値 (data[bottom] ) を中央(lower = upper の位置)に移動する
  temp = data[bottom]
  data[bottom] = data[upper]
  data[upper] = temp
data[bottom]にはこの時点でもう、最初に選択した値は入っていません。スワップされてしまっていますから。この3行の処理はじゃあどうすべきなのかというと、不要ですね。

次に、最も大事な点として、再帰の脱出条件が設定されていません。ですから絶対に再帰が終わりません。
メソッドの最初で、bottom>=topなら何もせずreturnと書く必要があります。これが再帰の脱出条件になります。
再帰部分はもっと簡略化できて、場合分けすることもなく
  # 真ん中に来た値の前半と後半で再びソート(再帰的処理)
  self.quick_sort(bottom, (upper - 1), data)
  self.quick_sort( (upper + 1), top, data)
で十分でしょう。

あと、ループの最後で
    lower = bottom
    upper = top
としているところ、これではループの継続条件が必ず満たされてしまうので無限再帰を解消しても無限ループですね。この2行も不要です。

全部まとめるとこんな感じ
# Sort モジュール(クイックソートとマージソートの処理で構成)
module Sort

# quick_sort メソッド
def self.quick_sort(bottom, top, data)
    
  if bottom<top

  lower = bottom
  upper = top

  #先頭の値を「適当な値 = div」とする(配列のいちばん最初の成分の値)
  div = data[bottom]

  #puts "data1 = " +div.to_s

  #puts "lower = " + lower.to_s + ", upper = " + upper.to_s

  # lower(下から上がっていく値)と upper (上から下がっていく値)が交わるまで繰り返し
  while lower < upper do

    while (lower < upper) && (data[lower] < div) do
      lower += 1
    end

    while (lower < upper) && (data[upper] > div) do
      upper -= 1
    end

    if lower < upper
      temp = data[lower]
      data[lower] = data[upper]
      data[upper] = temp
    else
      break
    end

  end

  # 真ん中に来た値の前半と後半で再びソート(再帰的処理)
    self.quick_sort(bottom, (upper - 1), data)
    self.quick_sort( (upper + 1), top, data)
end
end
# quick_sort メソッド終わり

end
#Sort モジュール終わり

#配列を生成し、ソートする(main 処理)

#配列の大きさを入力
puts "Number of index"
a = gets.to_i
N = a

# 要素数Nの配列を生成
sort_array = Array.new(N)

puts "Before sort"
# 1000以下の乱数を生成し、sort_array配列に格納
for i in 0..(N - 1) do
  sort_array[i] = Random.rand(1000)
end
p sort_array

puts "Sort is started"
# quick_sort メソッド呼び出し
Sort.quick_sort(0, (N - 1), sort_array)

puts "Sort ended"
p sort_array

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2015/10/06 23:56

    yuba さん、ご回答ありがとうございます。

    元ネタの本のソースを見返してみたところ、メソッド(関数)の最初に
    if(bottom >= top ){
    return;
    }

    とif 文が書かれており、これが再帰処理を掛ける際の終了判定となっていたことに気付きました。

    ソースを直してくださり、ありがとうございます。明日すぐに実行してみます。

    キャンセル

  • 2015/10/07 13:35

    yubaさん、ただいま実行終わりました。なによりエラーの原因は、quick_sort(再帰で用いる)メソッドの終了条件を示していないことでした。処理終了、という条件がある場合には、if 文で条件を示し、return とすればよかったんですね。勉強になりました。

    ありがとうございました。

    キャンセル

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

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

関連した質問

  • 解決済

    Ruby インスタンス変数を出力できない

    Rubyでインスタンス変数を出力したいのですが、どなたかサンプルコード付きで教えていただけないでしょうか? 宜しくお願いします!

  • 解決済

    1996年京都大学の入試問題について

    m, n は自然数で、m < n を満たすものとする。 m^n + 1, n^m + 1 がともに10の倍数となる m, n を 1組与えよ。 プログラミングで解いてください。 

  • 解決済

    rubyのunless文内にif分の条件を付け加えたときの実行の有無

    rubyの文法を勉強していて、自分なりに改造しようとして、実行されない理由がわかりませんでした。 puts "パスワードを入力してください" password = gets.ch

  • 解決済

    クイックソート

    前提・実現したいこと ここに質問したいことを詳細に書いてください 『アルゴリズムを、はじめよう」という書籍を参考に、Rubyでクイックソートのプログラムを書いています。この書籍

  • 解決済

    教科の平均点を出すアプリケーションをクラスを使って書き換えてみたいです。

    現在はインスタンスメソッドを使ったコードを構成しました。 このコードをクラスとインスタンスを使って書き換えたいです。 自分でも考えてみましたが手の付け所がわからず、よりよいコー

  • 受付中

    ruby とある問題での回答例。関数やクラス使えそうか?

    失礼します。 とある問題を説いていたら次のようなコードになりました。(問題の内容は拡散禁止されているため個人的な回答内容から読み取ってください。) ちなみに入力される値はこ

  • 受付中

    Ruby : メソッド定義について

    テキスト処理についてのコードです。 Rubyでテキスト処理をしているのですが、同じような繰り返しが2回あるので、なんとかメソッドにして綺麗にコードを書けないかなと思って、試して

  • 解決済

    クイックソートの処理内容

    『プログラミングの宝箱 アルゴリズムとデータ構造 第2版』(SBクリエイティブ株式会社)の内容の 第1章、クイックソートのjava版サンプルの以下の処理内容がわかりません。 文法的

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

  • Ruby

    7317questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • アルゴリズム

    392questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • ソート

    63questions

    複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

  • ループ

    49questions

    ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

  • トップ
  • Rubyに関する質問
  • ruby にてクイックソートのプログラムを作成しています。なぜか無限ループに陥ってしまいました。