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"
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/10/06 14:56
2015/10/07 04:35