Rubyで学ぶ選択ソート：仕組みの解説から実装まで徹底ガイド

※本記事は、Rubyでさまざまなソートアルゴリズムを学ぶシリーズの第2回です。第1回ではバブルソートを取り上げました。

この記事では、Rubyを使った選択ソート（Selection Sort）アルゴリズムの実装方法を順を追って解説します。選択ソートは「インプレース（in-place）型」の比較ソートアルゴリズムの一つで、ソート済みの要素が元のデータと同じ記憶領域をそのまま使用するのが特徴です。

はじめにお伝えしておきたいのですが、選択ソートはデータセットが小さい場合（10〜20要素程度）を除き、実務で使われることはほとんどありません。とはいえ、三輪車の乗り方を覚えてから自転車に挑むように、アルゴリズム学習の第一歩として最適な題材です。就職面接のコーディング課題で選択ソートの実装を求められたり、「なぜ選択ソートは大規模なデータセットに不向きなのか」を説明するよう問われる可能性もあります。ちなみに、選択ソートはこのシリーズ第1回で扱ったバブルソートよりは通常高いパフォーマンスを発揮します。

選択ソートの全体像

大まかに説明すると、選択ソートは配列を「ソート済みの領域」と「未ソートの領域」の2つに分けて処理を進めます。初期状態ではソート済み領域は空で、すべての要素が未ソート領域に含まれています。選択ソートでは2つのループを使用します。外側のループはn回（nは配列の要素数）繰り返され、毎回最初に「最小インデックス」を先頭の要素に設定します。その後、内側のループで各要素を比較し、現在の最小値より小さい要素が見つかれば最小インデックスを更新していきます。

言葉だけではイメージしにくいかもしれませんね。ご安心ください。次に具体的な例を見ていきましょう。

ステップ・バイ・ステップで理解する

まず、次の要素を持つ配列から始めます。[10, 30, 27, 7, 33, 15, 40, 50]

1回目の反復：最小の数値を見つける

この配列の最小値は7です。7を先頭に移動させ、代わりに10を7があった位置へ移動します。配列は次のようになります。[7, 30, 27, 10, 33, 15, 40, 50]

2回目の反復：次に小さい数値を見つける

今度はインデックス1の要素から探索を開始します（配列のインデックスは0始まりであることを忘れずに）。次に小さい要素は10です。10を配列の2番目の位置に移動し、30を10があった位置へ移動します。結果は次のとおりです。[7, 10, 27, 30, 33, 15, 40, 50]

以降も同じ手順を繰り返し、配列が完全にソートされるまで続けます。以下に、その後の各反復の結果を示します。

3回目：

[7, 10, 15, 30, 33, 27, 40, 50]

4回目：

[7, 10, 15, 27, 33, 30, 40, 50]

5回目：

[7, 10, 15, 27, 30, 33, 40, 50]

これで完全にソートできました！

視覚的に学びたい方のために、選択ソートの動作イメージを示した図の例をご覧ください。

画像出典

Rubyでの実装

以下がRubyで書いた選択ソート関数です。

def selection_sort(array)
  n = array.length - 1
  n.times do |i|
    min_index = i
    for j in (i + 1)..n
      min_index = j if array[j] < array[min_index]
    end
    array[i], array[min_index] = array[min_index], array[i] if min_index != i
  end
  puts array
end

それでは、このコードがどのように動作するのか詳しく見ていきましょう。

まず、変数nに要素数を代入します。ここで1を引いているのは、配列のインデックスが0始まりだからです。

次に、外側のループを作成します。このループはn回実行されます。

min_index = i

ここでは、最小インデックスを先頭位置の要素に設定しています。

for j in (i + 1)..n

続いて内側のループです。この行は「2番目の位置の要素からn番目の要素まで、以下の処理を行う」という意味になります。..演算子に馴染みがない方のために補足すると、これは始点から終点まで（両端を含む）の範囲オブジェクトを生成する演算子です。たとえば1..10は1から10までの範囲を作ります。

min_index = j if array[j] < array[min_index]

このループの中では、現在のmin_indexの要素より小さい要素が見つかった場合に、min_indexをその新しい要素の位置へ更新します。

array[i], array[min_index] = array[min_index], array[i] if min_index != i

内側のループを抜けたら、現在のmin_indexがiと等しいかどうかを確認します。等しくない場合は要素を入れ替える必要があります。array[i]にarray[min_index]を、array[min_index]にarray[i]を代入することで、先ほどの例で見たのと同じ「スワップ（交換）」を実現しています。

最後に、すべての処理が完了したら配列を出力します。これでソート済みの配列が得られます！

全体を組み合わせる

プログラム全体は次のようになります。

def selection_sort(array)
  n = array.length - 1
  n.times do |i|
    min_index = i
    for j in (i + 1)..n
      min_index = j if array[j] < array[min_index]
    end
    array[i], array[min_index] = array[min_index], array[i] if min_index != i
  end
  puts array
end

array = [10, 30, 27, 7, 33, 15, 40, 50]

selection_sort(array)

ターミナルでruby ruby-selection-sort.rbを実行すると、次の出力が得られます。

7
10
15
27
30
33
40
50

うまく動きましたね！

選択ソートが非効率な理由を理解する

アルゴリズムの効率を測る方法の一つが「ビッグオー記法（Big-O Notation）」です。ビッグオー記法は最悪ケースのパフォーマンスを表し、アルゴリズム同士を比較する際の指標となります。たとえば、ビッグオーがO(1)のアルゴリズムは、要素数nがどれだけ増えても最悪実行時間が一定であることを意味します。一方、O(n)のアルゴリズムは、nの増加に伴って最悪実行時間が線形に増加します。つまり、100個の要素を持つ配列をソートする際にO(n)とO(1)のアルゴリズムを選べるなら、O(1)の方が確実に優れているため、O(1)のアルゴリズムを選ぶべきだということです。

バブルソートと同様に、選択ソートもネストされた（入れ子になった）ループ構造のため、最悪計算量および平均計算量はO(n²)となります。これは、要素数が増えるほど効率が劇的に低下することを意味します。

まとめ

以上のことからもわかるように、選択ソートは実務で活躍する場面こそ少ないものの、コーディング課題で登場する可能性のある興味深いアルゴリズムです。また、選択ソートの関数を渡されて「ビッグオー記法では何になるのか、その理由は何か」を問われることもあるでしょう。この記事の例が、そうした場面に対応するための助けになれば幸いです。