はじめに
プログラミングの能力を高めるため、アルゴリズムの基礎を学びます。
いつもコードを書こうとすると、頭が真っ白な状態に陥ってしまいます。
その原因は足掛かりとなる知識がないからだと思います。
まず、地盤を築き、それ自体を使用もしくは応用したりできる思考力を身に付けることがゴールです。
内容
本記事は、挿入ソートを使って学習を進めます。
テスト
RSpecを利用してテストコードも実装しましたが、記事が長くなるため私のgo-on-ruby-algo-tripリポジトリにあります。
挿入ソート
初めに先頭要素を整列済みとみなし、以降の未整列から要素を1つ取り出し、整列済みの適切な場所に挿入します。それを末尾の要素まで繰り返していくことでソートするアルゴリズムです。
計算量
最良の場合O(n)、最悪・平均の場合O(n^2)。
使用例
計算量が大きいため、大規模データのソートには不向きです。
そのため主にアルゴリズム学習目的で用いられますが、要素数が少ない場合や、ほぼ整列済みのデータに対しては実務で使用されることがあります。
コード
def insertion_sort!(arr)
(1...arr.length).each do |i|
target = arr[i]
j = i - 1
while j >= 0 && arr[j] > target
arr[j + 1] = arr[j]
j-= 1
end
arr[j + 1] = target
end
arr
end
「処理の流れ」
未整列部分の先頭要素を整列済み部分の末尾から前方へ向かって比較していきます。そこで、整列済みが未整列より大きい要素であれば1つ右にシフトさせていきます。それを小さい要素まで繰り返し行い、空いた部分に未整列の要素を挿入します。
「ベンチマークテスト」
最良・最悪・平均の3つのケースを用いて、挿入ソートの計算量の違いが実行時間にどのように表れるかテストしました。
require "benchmark"
arr_asce = (1..10_000).to_a
arr_desc = (1..10_000).to_a.reverse
arr_rand = (1..10_000).to_a.shuffle
Benchmark.bmbm do |x|
x.report("best case: ") { insertion_sort!(arr_asce.dup) }
x.report("worst case: ") { insertion_sort!(arr_desc.dup) }
x.report("average case:") { insertion_sort!(arr_rand.dup) }
end
結果からわかる通り、3つのケースで実行時間に大きな差が見られます。
これは、昇順に並んだ最良ケースの配列の場合、各要素について1回の比較で処理が終了するため、計算量がO(n)となるからです。
一方、降順に並んだ最悪ケースの配列の場合、i番目の要素に対してi回の比較とシフトが発生し、これを全要素で繰り返すため、計算量がO(n^2)となります。
平均ケースの配列も、最悪ケースと同様の処理を繰り返すことがあるため、実行時間が近い値となり計算量がO(n^2)であるとわかります。
user system total real
best case: 0.001506 0.000000 0.001506 ( 0.001497)
worst case: 3.127033 0.000000 3.127033 ( 3.133326)
average case: 1.572029 0.000000 1.572029 ( 1.574649)
おわりに
挿入ソートは、要素を交換していくバブルソートや選択ソートとは異なる発想で、要素をシフトさせながら整列させるソートアルゴリズムであるとわかりました。