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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

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

アルゴリズム

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

ソート

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

ループ

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

Q&A

解決済

1回答

2647閲覧

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

shocyu

総合スコア17

Ruby

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

アルゴリズム

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

ソート

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

ループ

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

0グッド

0クリップ

投稿2015/10/06 09:17

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

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

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

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

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

よろしくお願いします。ソースは以下になります。

ruby

1# Sort モジュール(クイックソートとマージソートの処理で構成) 2module Sort 3 4# quick_sort メソッド 5def self.quick_sort(bottom, top, data) 6 7 lower = bottom 8 upper = top 9 10 temp = 0.0 11 div = 0.0 12 13 #先頭の値を「適当な値 = div」とする(配列のいちばん最初の成分の値) 14 div = data[bottom] 15 16 #puts "data1 = " +div.to_s 17 18 #puts "lower = " + lower.to_s + ", upper = " + upper.to_s 19 20 # lower(下から上がっていく値)と upper (上から下がっていく値)が交わるまで繰り返し 21 while lower < upper do 22 23 while (lower < upper) && (data[lower] < div) do 24 lower += 1 25 puts "lower = " + lower.to_s 26 27 if lower == upper 28 break 29 end 30 end 31 32 while (lower < upper) && (data[upper] > div) do 33 upper -= 1 34 puts "upper =" + upper.to_s 35 36 if upper == lower 37 break 38 end 39 end 40 41 if lower < upper 42 temp = data[lower] 43 data[lower] = data[upper] 44 data[upper] = temp 45 else 46 break 47 end 48 49 p data 50 lower = bottom 51 upper = top 52 53 end 54 55 # 最初に選択した値 (data[bottom] ) を中央(lower = upper の位置)に移動する 56 temp = data[bottom] 57 data[bottom] = data[upper] 58 data[upper] = temp 59 p data 60 61 # 真ん中に来た値の前半と後半で再びソート(再帰的処理) 62 #(例外処理)upper(真ん中の地点)が bottom かその1つ上の場合 -> 後半だけ再びソート 63 if upper <= bottom + 1 64 self.quick_sort( (upper + 1), top, data) 65 #(例外処理)upper が top かその1つ下の場合 -> 前半だけ再びソート 66 elsif upper >= top -1 67 self.quick_sort( bottom, (upper - 1), data) 68 #(それ以外)前半、後半とも再びソート 69 else 70 self.quick_sort(bottom, (upper - 1), data) 71 self.quick_sort( (upper + 1), top, data) 72 end 73 74end 75# quick_sort メソッド終わり 76 77end 78#Sort モジュール終わり 79 80#配列を生成し、ソートする(main 処理) 81 82#配列の大きさを入力 83puts "Number of index" 84a = gets.to_i 85N = a 86 87# 要素数Nの配列を生成 88sort_array = Array.new(N) 89 90puts "Before sort" 91# 1000以下の乱数を生成し、sort_array配列に格納 92for i in 0..(N - 1) do 93 94 sort_array[i] = Random.rand(1000) 95 print sort_array[i].to_s + ", " 96end 97 98puts "\n" 99 100puts "Sort is started" 101# quick_sort メソッド呼び出し 102Sort.quick_sort(0, (N - 1), sort_array) 103 104puts "Sort ended" 105for i in 0..(N -1) do 106 print sort_array[i].to_s + ", " 107end 108 109puts "\n"

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

まずここ

Ruby

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

data[bottom]にはこの時点でもう、最初に選択した値は入っていません。スワップされてしまっていますから。この3行の処理はじゃあどうすべきなのかというと、不要ですね。

次に、最も大事な点として、再帰の脱出条件が設定されていません。ですから絶対に再帰が終わりません。
メソッドの最初で、bottom>=topなら何もせずreturnと書く必要があります。これが再帰の脱出条件になります。
再帰部分はもっと簡略化できて、場合分けすることもなく

Ruby

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

で十分でしょう。

あと、ループの最後で

Ruby

1 lower = bottom 2 upper = top

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

全部まとめるとこんな感じ

Ruby

1# Sort モジュール(クイックソートとマージソートの処理で構成) 2module Sort 3 4# quick_sort メソッド 5def self.quick_sort(bottom, top, data) 6 7 if bottom<top 8 9 lower = bottom 10 upper = top 11 12 #先頭の値を「適当な値 = div」とする(配列のいちばん最初の成分の値) 13 div = data[bottom] 14 15 #puts "data1 = " +div.to_s 16 17 #puts "lower = " + lower.to_s + ", upper = " + upper.to_s 18 19 # lower(下から上がっていく値)と upper (上から下がっていく値)が交わるまで繰り返し 20 while lower < upper do 21 22 while (lower < upper) && (data[lower] < div) do 23 lower += 1 24 end 25 26 while (lower < upper) && (data[upper] > div) do 27 upper -= 1 28 end 29 30 if lower < upper 31 temp = data[lower] 32 data[lower] = data[upper] 33 data[upper] = temp 34 else 35 break 36 end 37 38 end 39 40 # 真ん中に来た値の前半と後半で再びソート(再帰的処理) 41 self.quick_sort(bottom, (upper - 1), data) 42 self.quick_sort( (upper + 1), top, data) 43end 44end 45# quick_sort メソッド終わり 46 47end 48#Sort モジュール終わり 49 50#配列を生成し、ソートする(main 処理) 51 52#配列の大きさを入力 53puts "Number of index" 54a = gets.to_i 55N = a 56 57# 要素数Nの配列を生成 58sort_array = Array.new(N) 59 60puts "Before sort" 61# 1000以下の乱数を生成し、sort_array配列に格納 62for i in 0..(N - 1) do 63 sort_array[i] = Random.rand(1000) 64end 65p sort_array 66 67puts "Sort is started" 68# quick_sort メソッド呼び出し 69Sort.quick_sort(0, (N - 1), sort_array) 70 71puts "Sort ended" 72p sort_array

投稿2015/10/06 13:59

yuba

総合スコア5568

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

shocyu

2015/10/06 14:56

yuba さん、ご回答ありがとうございます。 元ネタの本のソースを見返してみたところ、メソッド(関数)の最初に if(bottom >= top ){ return; } とif 文が書かれており、これが再帰処理を掛ける際の終了判定となっていたことに気付きました。 ソースを直してくださり、ありがとうございます。明日すぐに実行してみます。
shocyu

2015/10/07 04:35

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問