【C言語】選択ソートのアルゴリズムと実装方法をわかりやすく解説

選択ソート（Selection Sort）は、比較ベースの基本的なソートアルゴリズムの一つです。配列の中から最小値を見つけて先頭の位置に移動させ、その操作を繰り返すことで配列全体を昇順に並べ替えます。次回以降の走査では、すでに確定した位置の次の要素から探索を開始するのがポイントです。

具体例で仕組みを理解する

配列 {6, 3, 8, 12, 9} を例に考えてみましょう。この配列の最小値は「3」なので、3を先頭に移動すると配列は {3, 6, 8, 12, 9} となります。

次に再び最小値を探しますが、今回はすでに確定済みの「3」は探索対象から除外します。次の最小値である「6」が見つかったら、それを2番目の位置に配置します。この操作を配列が完全にソートされるまで繰り返していきます。

選択ソートの動作手順

ここでは、配列 {20, 12, 23, 55, 21} を使って、選択ソートの処理の流れをステップごとに見ていきましょう。

反復1

• 配列の最初の要素を最小値として設定します。
  最小値 = 20
• 最小値を次の要素と比較し、より小さい要素があればそれを新しい最小値とします。これを配列の末尾まで繰り返します。
  12との比較：20 > 12 → 最小値 = 12
  23との比較：12 < 23 → 最小値 = 12
  55との比較：12 < 55 → 最小値 = 12
  21との比較：12 < 21 → 最小値 = 12
• 最小値を配列の先頭（インデックス0）に配置します。
  配列 = {12, 20, 23, 55, 21}

反復2

次の反復では、最初の未ソート要素、つまり最小値を配置した位置の次の要素から探索を開始します。

• 最小値 = 20
  23との比較：20 < 23 → 最小値 = 20
  55との比較：20 < 55 → 最小値 = 20
  21との比較：20 < 21 → 最小値 = 20
• 最小値はすでに正しい位置にあるため、変更はありません。
  配列 = {12, 20, 23, 55, 21}

反復3

• 最小値 = 23
  55との比較：23 < 55 → 最小値 = 23
  21との比較：23 > 21 → 最小値 = 21
• 最小値をインデックス2に移動します。
  配列 = {12, 20, 21, 55, 23}

反復4

• 最小値 = 55
  23との比較：23 < 55 → 最小値 = 23
• 最小値をインデックス3に移動します。
  配列 = {12, 20, 21, 23, 55}

これで配列のソートが完了しました。

C言語による実装例

#include <stdio.h>
int main() {
    int arr[10]={6,12,0,18,11,99,55,45,34,2};
    int n=10;
    int i, j, position, swap;
    for (i = 0; i < (n - 1); i++) {
        position = i;
        for (j = i + 1; j < n; j++) {
            if (arr[position] > arr[j])
                position = j;
        }
        if (position != i) {
            swap = arr[i];
            arr[i] = arr[position];
            arr[position] = swap;
        }
    }
    for (i = 0; i < n; i++)
        printf("%d\t", arr[i]);
    return 0;
}

実行結果

0  2  6  11  12  18  34  45  55  99

選択ソートの計算量

選択ソートの時間計算量は、データの初期状態に関わらず最良・平均・最悪のいずれの場合も O(n²) です。これは、各反復で未ソート部分のすべての要素と比較を行うためです。

一方、必要な追加メモリは定数個の変数のみで済むため、空間計算量は O(1) です。また、交換回数が最大でも n−1 回と少ないため、データの書き換えコストが高い場面では有利になることもあります。要素数が少ない配列や、学習用としてシンプルなソートを理解したい場合に適したアルゴリズムといえるでしょう。