ruby にてマージソートのアルゴリズムを書いています。どうも詰めが甘いようです。

Question

ruby で使えるアルゴリズムのライブラリを製作すべく、マージソートのアルゴリズムを書いてみました。

エラーは修復されたのですが、どうも詰めが甘いようで、正しい結果が出力されません。余計な処理が入っているかと思われます。

ソースは以下になります。もし不要な処理や足りない部分がありましたらご指摘お願いします。

# Sort モジュール（クイックソートとマージソートの処理で構成）
module Sort

#merge_sort メソッド（マージソート）
#引数 (n, x) = (配列の要素の数、ソートする配列）
def self.merge_sort(n, x)

  i, j, k, m = 0, 0, 0, 0

  if n <= 1
    return
  end

  m = n / 2

  buffer = x[m..(n - 1)]

  # ブロックを前半と後半に分けてソート（再帰呼び出し）
  merge_sort(m, x)
  merge_sort(n - m, buffer)

  # x の前半を x の後半にコピー
  x[(n - m)..(n - 1)] = x[0..(m - 1)]

  j = n - m

  # buffer（ブロックの後半をソートした配列）とｘの後半とで比較して、小さい方をｘの前半に入れる
  while i < m && j < n do
    if buffer[i] <= x[j]
      x[k] = buffer[i]
      k += 1
      i += 1
    else
      x[k] = x[j]
      k += 1
      j += 1
    end
  end

  while i < m do
    x[k] = buffer [i]
    k += 1
    i += 1
  end

  #p x

end
# merge_sort メソッド終わり

end
#Sort モジュール終わり

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

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

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

puts "Before sort"
# １０００以下の乱数を生成し、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.merge_sort(N, sort_array)

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

puts "\n"

Answer 1

間違いの指摘だけでは質問者さんの「ため」にならないので、敢えて遠回しに説明します。

配列[3,1,2]を渡したときの挙動を追ってみてください。
前半、後半のソート後、最初のループに入る前の変数の状態は
x = 3,1,3
buffer = 1,2
i,j,k,m,n=0,2,0,1,3
ですね。ループを1回実行すると、
x = 1, 1, 3
buffer = 1, 2
i,j,k,m,n=1,2,1,1,3
ですね。再度、条件をチェックすると、満たしませんね。
次のループも見てみましょう。これも条件を満たさないですね。

…あれあれ、関数が終わってしまいました。
bufferの一部分のコピーが終わっていませんね。
よく考えてみましょう。bufferの長さっていくつでしたっけ?
そうです、n-mです。mではありません。
配列の長さが奇数のときに、挙動がおかしくなっていたのですね。

…長ったらしく机上デバッグしましたが、要はそういうことです。

Comments

[shigemi_sano]

majiponi　さん、丁寧な解説ありがとうございます。返信遅れてすみません。修正して実行してからお返事したいと思い、今となりました。

マージソートにおいては、配列の長さが奇数の時が問題、ということを押さえて、最もシンプルな例を用いて間違いを検出する、という方法が必要だったことに気付かされました。

次に同じような不具合が生じた場合には、ここでご指摘いただいた形でデバッグが出来るようにしてまいります。ありがとうございました。