はじめに
プログラミングの能力を高めるため、アルゴリズムの基礎を学びます。
いつもコードを書こうとすると、頭が真っ白な状態に陥ってしまいます。
その原因は足掛かりとなる知識がないからだと思います。
まず、地盤を築き、それ自体を使用もしくは応用したりできる思考力を身に付けることがゴールです。
内容
本記事は、分割統治法の1種であるクイックソートを使って学習を進めます。
テスト
RSpecを利用してテストコードも実装しましたが、記事が長くなるため私のgo-on-ruby-algo-tripリポジトリにあります。
クイックソート
クイックソートは、基準となるピボット値(要素)を選び、他の要素をピボットより大きいか小さいかで比較してグループに分割し、それぞれのグループに対して同じ処理を再帰的に繰り返すことでソートを行うアルゴリズムです。
計算量
平均計算量はO(n log n)ですが、最悪の場合はO(n^2)となります。
例えば、すでに昇順や降順に並んでいる配列に対して、ピボット値として毎回最大値または最小値を選んでしまうと最悪のケースになります。これは、ピボットと未処理の全要素を比較する処理が再帰的に繰り返されるためです。
使用例
クイックソートは、配列など主記憶上のデータを高速に整列する内部ソートとして、多くのプログラムで利用されています。
コード
def quick_sort!(arr, left = 0, right = arr.length - 1)
return if left >= right
pivot = arr[(left + right) / 2]
i = left
j = right
while i <= j
i += 1 while i <= j && arr[i] < pivot
j -= 1 while i <= j && arr[j] > pivot
if i <= j
arr[i], arr[j] = arr[j], arr[i]
i += 1
j -= 1
end
end
quick_sort!(arr, left, j)
quick_sort!(arr, i, right)
arr
end
「処理の流れ」
まず配列の中央の値をピボットとして選びます。その後、左右からインデックス(iとj)を動かしながら、ピボットより小さい値は左側、大きい値は右側に移動させます。
whileループが終了した時点で、インデックスiとjが左右の境界を示すため、この範囲を使って次の再帰呼び出しでグループを決めます。
つまり、インデックス操作によって「分割された一時的なグループ範囲」を決め、その範囲を再帰でさらにソートしていく形になります。
「マージソートとの比較」
マージソートでは、再帰処理によって配列を要素数1になるまで2分割し、再帰の戻りのタイミングで要素を比較しマージしていました。
クイックソートは、配列全体をピボット値を元に論理的に左右に分割し、比較・入れ替えを行います。これを各グループにも要素数が1になるまで行います。
つまり、マージソートは分割と比較をほぼ同時に行っています。
おわりに
頭の中では簡単に思えるロジックでも、実際に自分で実装してみると非常に苦労しました。
とくに、インデックス操作で手間取りました。比較演算子の微妙な使い方の違いに翻弄される場面も多くありました。