はじめに
プログラミングの能力を高めるため、アルゴリズムの基礎を学びます。
いつもコードを書こうとすると、頭が真っ白な状態に陥ってしまいます。
その原因は足掛かりとなる知識がないからだと思います。
まず、地盤を築き、それ自体を使用もしくは応用したりできる思考力を身に付けることがゴールです。
内容
本記事は、分割統治法の一種であるマージソートを使って学習を進めます。
テスト
RSpecを利用してテストコードも実装しましたが、記事が長くなるため私のgo-on-ruby-algo-tripリポジトリにあります。
マージソート
マージソートとは、データを分割して要素数1の配列(常に整列済み)を作り、整列済み配列同士をマージする操作を繰り返すことで、全体を整列する分割統治法に基づくソートアルゴリズムである。
計算量
要素数nの配列を1になるまで2で分割していくと、n / 2^k = 1となるため、分割の深さはk = log₂ nです。各段階において、分割された配列全体に対してマージ処理を行うため、1段あたりの処理量はnとなります。したがって、分割の段数log n × 各段の処理量nより、マージソートの計算量はO(n log n)となります。
使用例
マージソートは、データがメモリに収まりきらないほど巨大な場合(ログやDBレコードなど)に、ディスクを作業領域として用いる外部ソートで利用されます。
外部ソートでは、まずメモリに収まる単位でデータを読み込みソートした後、整列済みの部分列(run)としてディスクに書き出します。
マージソートは、これら複数の整列済みデータを順次アクセスのみで統合(マージ)できるため、ランダムアクセスが高コストなディスク環境に適しています。
コード : 「トップダウン型」
# 配列を再帰的に分割し、マージソートで昇順に並び替え
def merge_sort(arr)
return arr if arr.length <= 1
middle = arr.length / 2
left = merge_sort(arr[0...middle])
right = merge_sort(arr[middle...arr.length])
merge(left, right)
end
# 2つのソート済み配列を、1つのソート済み配列に統合
def merge(left, right)
result = []
i = 0
j = 0
while i < left.length && j < right.length
if left[i] <= right[j]
result << left[i]
i += 1
else
result << right[j]
j += 1
end
end
result.concat(left[i..])
result.concat(right[j..])
result
end
# 配列をマージソートして返すラッパーメソッド
def sort_array(arr)
merge_sort(arr)
end
「処理の流れ」
1つの配列を中央値で二分し、それぞれの配列要素が1になるまで再帰的に分割します。
要素数1の配列は常にソート済みであるため、2つのソート済み配列を先頭から比較しながら統合することで、より大きなソート済み配列を順に構築していきます。
このマージ処理を再帰の戻りとともに繰り返すことで、最終的に全体がソートされます。
コード : 「ボトムアップ型」
# 再帰を使わず、ボトムアップ方式で配列をマージソート
def merge_sort_by_bottom_up(arr)
n = arr.length
buffer = Array.new(n)
width = 1
while width < n
i = 0
while i < n
left = i
mid = [i + width, n].min
right = [i + width * 2, n].min
merge_range(arr, buffer, left, mid, right)
i += width * 2
end
arr, buffer = buffer, arr
width *=2
end
arr
end
# ソート済み配列を、bufferにマージして書き込む
def merge_range(arr, buffer, left, mid, right)
i = left
j = mid
k = left
while i < mid && j < right
if arr[i] <= arr[j]
buffer[k] = arr[i]
i += 1
else
buffer[k] = arr[j]
j += 1
end
k += 1
end
while i < mid
buffer[k] = arr[i]
i += 1
k += 1
end
while j < right
buffer[k] = arr[j]
j += 1
k += 1
end
end
# ボトムアップ版マージソートのラッパーメソッド
def sort_array(arr)
merge_sort_by_bottom_up(arr)
end
「処理の流れ」
AIに別解を教えてもらいました。
この方法では、1つの配列を仮想的に要素数1のソート済み配列だとみなし、それらを隣り合う部分ごとに比較・統合することで、より大きなソート済み配列を順に構築していきます。
私のコードは、大きい配列を再帰的に分解し小さくし、それらをマージしながら元のサイズに戻していくトップダウン型のマージソートでした。
一方この方法は、小さい配列から初めて徐々に大きな配列を構築していくボトムアップ型のマージソートです。再帰は使わず、補助配列(buffer)を1つ用意して使い回すことでソートを行います。
おわりに
今回マージソートを学習したことで、これまで基本情報技術者試験の知識として名前や計算量だけを理解していたソートアルゴリズムを、実際の利用シーン(外部ソートやDB・ストレージとの関係)と結びつけて捉え直すことができました。
今後は、クイックソートやヒープソートなど他のソートアルゴリズムについても学習していきたいと思います。