C言語における選択ソートの仕組みと実装方法をわかりやすく解説

選択ソート（Selection Sort）は、配列の中から最小値を探し出し、それを先頭の位置に配置していくソートアルゴリズムです。次の走査では、最小値を配置した位置の次のインデックスから開始し、これを繰り返すことで配列全体を昇順に並べ替えます。

選択ソートの基本手順

1. 要素のリストの中から最小の要素を選び、先頭の位置に配置します。
2. 残りの要素に対して同じ操作を繰り返し、すべての要素がソートされるまで続けます。

ここでは、以下のリストを例に具体的な動作を見ていきましょう。

30 50 40 10 20

1回目のパス

最小値の候補を sm = a[0] = 30 とします。

a[1] < sm → 50 < 30（偽）→ sm は 30 のまま
a[2] < sm → 40 < 30（偽）→ sm は 30 のまま
a[3] < sm → 10 < 30（真）→ sm を 10 に更新
a[4] < sm → 20 < 10（偽）→ sm は 10 のまま

最後に a[0] と最小値 sm（10）を交換します。

10 50 40 30 20

2回目のパス

最小値の候補を sm = a[1] = 50 とします。

a[2] < sm → 40 < 50（真）→ sm を 40 に更新
a[3] < sm → 30 < 40（真）→ sm を 30 に更新
a[4] < sm → 20 < 30（真）→ sm を 20 に更新

a[1] と最小値 sm（20）を交換します。

10 20 40 30 50

3回目のパス

最小値の候補を sm = a[2] = 40 とします。

a[3] < sm → 30 < 40（真）→ sm を 30 に更新
a[4] < sm → 50 < 30（偽）→ sm は 30 のまま

a[2] と最小値 sm（30）を交換します。

10 20 30 40 50

4回目のパス

最小値の候補を sm = a[3] = 40 とします。

a[4] < sm → 50 < 40（偽）→ sm は 40 のまま

a[3] と最小値 sm（40）を交換します。

10 20 30 40 50

これですべての要素が昇順に並び替えられ、ソートが完了しました。

選択ソートのアルゴリズム手順

選択ソートの一般的な処理手順は、以下の擬似コードのように表せます。

for (i = 0; i < n-1; i++) {
    sm = i;
    for (j = i+1; j < n; j++) {
        if (a[j] < a[sm])
            sm = j;
    }
    t = a[i];
    a[i] = a[sm];
    a[sm] = t;
}

C言語による実装例

以下は、選択ソートの手法を実装したC言語のプログラムです。

#include <stdio.h>
int main(){
    int a[50], i, j, n, t, sm;
    printf("enter the No: of elements in the list:\n");
    scanf("%d", &n);
    printf("enter the elements:\n");
    for(i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    for (i = 0; i < n-1; i++){
        sm = i;
        for (j = i+1; j < n; j++){
            if (a[j] < a[sm]){
                sm = j;
            }
        }
        t = a[i];
        a[i] = a[sm];
        a[sm] = t;
    }
    printf("after selection sorting the elements are:\n");
    for (i = 0; i < n; i++)
        printf("%d\t", a[i]);
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、以下のような結果が得られます。

enter the No: of elements in the list:
4
enter the elements:
45
12
37
68
after selection sorting the elements are:
12 37 45 68

選択ソートの計算量と特徴

選択ソートの計算量は以下のとおりです。

• 最悪計算量：O(n²)
• 平均計算量：O(n²)
• 最良計算量：O(n²)
• 空間計算量：O(1)（インプレースソート）

選択ソートは実装がシンプルで動作を理解しやすい反面、要素数が多いデータには不向きです。その一方で、交換回数が最大でも n−1 回と少ないという特徴があり、要素の入れ替えコストが高い場面では有利に働きます。