【基本情報技術者試験】選択ソート問題をC言語のコードで確認してみよう！

以前、「バブルソート問題をC言語のコードで確認してみよう！」で、パスごとの状態変化を追いながらトレース問題の解き方を確認した。今回はソートアルゴリズムの2本目、「選択ソート」を同じ切り口で扱う。

基本情報技術者試験では、バブルソートだけでなく選択ソートのトレース問題も頻出である。動きは似ているようで実は違うため、「何を確定させながら進むのか」を混同しないことが今回の目的である。

今回使うコード（選択ソート）

#include <stdio.h>

#define SIZE 6

void print_array(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void selection_sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int min_idx = i; /* このパスでの最小値の位置を記録 */

        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }

        printf("%d回目のパス後: ", i + 1);
        print_array(arr, size);
    }
}

int main(void) {
    int data[SIZE] = {5, 2, 8, 1, 9, 3};

    printf("ソート前: ");
    print_array(data, SIZE);

    selection_sort(data, SIZE);

    printf("ソート後: ");
    print_array(data, SIZE);

    return 0;
}

実行結果

ソート前: 5 2 8 1 9 3
1回目のパス後: 1 2 8 5 9 3
2回目のパス後: 1 2 8 5 9 3
3回目のパス後: 1 2 3 5 9 8
4回目のパス後: 1 2 3 5 9 8
5回目のパス後: 1 2 3 5 8 9
ソート後: 1 2 3 5 8 9

バブルソートと違い、選択ソートには早期終了のフラグが存在しない。必ずsize-1回のパスをすべて実行するという点が、まず押さえておきたい違いである。

【トレースしてみよう】パスごとに何が起きているか

配列 {5, 2, 8, 1, 9, 3} に対して、1回目のパス（i=0）で内側ループが何をしているかを確認する。

内側ループが終わった時点でmin_idxは3。ここで初めてarr[0]とarr[3]を交換し、1回目のパスが完了する。

ここがバブルソートとの決定的な違いである。バブルソートは比較のたびに交換が発生しうるが、選択ソートは1回のパスで交換が起きるのは最大1回だけである。トレース問題では、この「交換のタイミングがループの最後にしか来ない」という構造を問う設問が出やすい。

試験問題を解くときの読み方のコツ

1. 外側ループが「確定させる位置」、内側ループが「その位置に入れる最小値を探す範囲」を表していることをまず押さえる
2. 交換処理が内側ループの外（＝パスの最後）にあることを確認する。もし交換処理が内側ループの中にあれば、それは選択ソートではなく別のアルゴリズムである
3. min_idxのような「候補を記録する変数」が出てきたら、「今のところの最小値の位置」を指していると読み取り、それが内側ループのどの条件で更新されるかを追う
4. 穴埋め問題では、min_idxが最後にどの値になっているかを先に確定させてから、交換後の配列を埋めると間違いにくい

計算量の確認（頻出ポイント）

配列サイズをnとすると、比較回数はバブルソートと同じく

(n-1) + (n-2) + ... + 1 = n(n-1)/2

でO(n²)である。一方で交換回数は最大n-1回にとどまり、この点がバブルソートとの比較で問われやすい。「計算量は同じでも、実際の交換コストは異なる」というのが選択ソートの試験対策上のポイントである。

まとめ

• 選択ソートは、外側ループで確定位置を進めながら、内側ループで最小値の位置を探すという構造である
• バブルソートと違い、早期終了の仕組みがなく、必ずsize-1回のパスを実行する
• 交換回数がバブルソートより少ない点が、比較問題での頻出ポイントである

次回は「挿入ソート」を取り上げ、整列済み部分に要素を挿入していくタイプのソートを同じくトレース問題形式で確認していく。

この記事で扱ったコードは、GitHubの c-language-studies リポジトリ
（FE-algorithm/03_selection_sort/c/）で公開している。