はじめに
プログラミングの能力を高めるため、アルゴリズムの基礎を学びます。
いつもコードを書こうとすると、頭が真っ白な状態に陥ってしまいます。
その原因は足掛かりとなる知識がないからだと思います。
まず、地盤を築き、それ自体を使用もしくは応用したりできる思考力を身に付けることがゴールです。
内容
本記事は、バブルソートを使って学習を進めます。
テスト
RSpecを利用してテストコードも実装しましたが、記事が長くなるため私のgo-on-ruby-algo-tripリポジトリにあります。
バブルソート
バブルソートとは、隣同士の要素を比較し、大きいまたは小さい要素を端へ移動させることを繰り返すソートアルゴリズムです。
計算量
一般的なバブルソートでは、配列の状態に関わらず比較を繰り返すため、最良・平均・最悪いずれの場合も計算量はO(n^2)。
使用例
計算量が大きいため、実務ではほとんど使用されず、主にアルゴリズム学習目的で用いられます。
コード
def bubble_sort!(arr)
loop do
swapped = false
(arr.length - 1).times do |i|
if arr[i] > arr[i + 1]
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = true
end
end
break unless swapped
end
arr
end
「処理の流れ」
配列の先頭から隣接する要素同士を順に比較し、前方の要素が大きい値の場合はそれらを交換します。この操作を配列の末尾まで行い、交換が発生しなくなるまで繰り返すことで配列を整列させます。
「フラグで効率化」
swappedは、ループ内で交換が発生したかどうかを示すフラグです。
もし、そのループ内で1度も交換が発生しなければ、配列は完全に整列済みと判断できるので、処理を早期に終了できます。
これにより、常にn回ループする必要がなくなり、無駄なループを避けられます。ただし、配列が完全に逆順の場合(降順の配列を昇順にソートする場合など)には、比較・交換が毎回発生するため計算量はO(n^2)になります。
「ベンチマークテスト」
先に示したbubble_sort!を用いて、最良・最悪・平均の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: ") { bubble_sort!(arr_asce.dup) }
x.report("worst case: ") { bubble_sort!(arr_desc.dup) }
x.report("average case:") { bubble_sort!(arr_rand.dup) }
end
結果からわかる通り、3つのケースで実行時間に大きな差が見られます。
これは、昇順に並んだ最良ケースの配列の場合、1回目のループ内で比較は行われるものの交換が一度も発生せずswappedがfalseとなり処理が終了するため、計算量がO(n)となるからです。
一方、降順に並んだ最悪ケースの配列の場合、各ループでほぼ全要素について比較と交換が発生し、これを配列全体に対して繰り返すため、計算量がO(n^2)となります。
平均ケースの配列も、最悪ケースと同様の処理を繰り返すことがあるため、実行時間が近い値となり計算量がO(n^2)であるとわかります。
user system total real
best case: 0.000815 0.000007 0.000822 ( 0.000895)
worst case: 11.189437 0.023976 11.213413 ( 11.234721)
average case: 9.555767 0.011899 9.567666 ( 9.574211)
おわりに
ループ処理は条件式だけで制御するものだと思っていましたが、フラグを用いることでより柔軟に分岐させられることを理解しました。