【Ruby】選択ソートでアルゴリズムを学ぶ

はじめに

プログラミングの能力を高めるため、アルゴリズムの基礎を学びます。
いつもコードを書こうとすると、頭が真っ白な状態に陥ってしまいます。
その原因は足掛かりとなる知識がないからだと思います。
まず、地盤を築き、それ自体を使用もしくは応用したりできる思考力を身に付けることがゴールです。

内容
本記事は、選択ソートを使って学習を進めます。

テスト
RSpecを利用してテストコードも実装しましたが、記事が長くなるため私のgo-on-ruby-algo-tripリポジトリにあります。

選択ソート

選択ソートは、配列の先頭から順番に位置を確定させるソートアルゴリズムです。
配列の中から最小値を選んで先頭と交換し、先頭要素を整列済みとします。次に、その位置以降で最小値を探し、未整列部分の先頭と交換します。この処理を繰り返すことで配列全体を整列します。

比較回数は基本ソートアルゴルズムであるバブルソートとほぼ同程度だが、1回のループにつき交換は最大1回のため、交換回数は少ないです。

計算量
最良・最悪・平均いずれの場合も計算量はO(n^2)。

使用例
計算量が大きいため、実務ではほとんど使用されず、主にアルゴリズム学習目的で用いられます。

コード

def selection_sort!(arr, verbose: false)
  n = arr.length
  swap_count = 0

  (0...n - 1).each do |i|
    min_index = i
    # puts "==#{i}回目：探索開始=="
    
    (i + 1...n).each do |j|
      if arr[j] < arr[min_index]
        min_index = j
        # puts "最小値更新 → index:#{min_index}, 値:#{arr[min_index]}"
      end
    end
    if min_index != i
      # puts "交換 → #{i} と #{min_index}"
      arr[i], arr[min_index] = arr[min_index], arr[i]
      # puts "結果 #{arr}"
      swap_count += 1
    else
      # puts "交換なし"
    end
  end

  if verbose
    { array: arr, swap: swap_count }
  else
    arr
  end
end

「処理の流れ」

外側のループで未整列部分の先頭位置を固定し、内側ループ内で未整列部分から最小値のインデックスを探索します。その後、未整列部分の先頭要素と交換します。この処理を配列末尾まで繰り返すことで、配列全体を整列させます。

「ベンチマークテスト」

最良・最悪・平均の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:    ") { selection_sort!(arr_asce.dup) }
  x.report("worst case:   ") { selection_sort!(arr_desc.dup) }
  x.report("average case: ") { selection_sort!(arr_rand.dup) }
end

結果からわかる通り、3つケースで実行時間に大きな差は見られませんでした。
これは、選択ソートが配列の並びに関係なく同程度の処理を行うため、3つのケースいずれも計算量がO(n^2)となることを示しています。

                     user     system      total        real
best case:       3.210869   0.000000   3.210869 (  3.216703)
worst case:      3.290988   0.000000   3.290988 (  3.302391)
average case:    3.223871   0.001811   3.225682 (  3.232090)

おわりに

選択ソートの実装自体は簡単でしたが、最終形に至るまでにいくつかの問題点がありました。例えば、先頭と同値の場合でも交換を行っていたり、最小値を見つける度に先頭と交換してしまったりと、無駄な処理が含まれていました。

これらの問題は、処理毎にputsを用いて途中経過を確認することで発見・修正できました。
一見正しい結果を導けているようでも、意図しない処理が行われていることがある、と分かりました。