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

前回、「選択ソート問題をC言語のコードで確認してみよう！」で、最小値を探して確定させていくタイプのソートを扱った。今回はソートアルゴリズムの3回目、「挿入ソート」を同じくトレース問題形式で確認する。

挿入ソートは、これまでの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 insertion_sort(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        int key = arr[i]; /* これから挿入する値を退避しておく */
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; /* keyより大きい値を1つ後ろにずらす */
            j--;
        }
        arr[j + 1] = key; /* 空いた位置にkeyを挿入 */

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

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

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

    insertion_sort(data, SIZE);

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

    return 0;
}

実行結果

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

バブルソート・選択ソートは「配列の前から末尾に向かって走査する」動きだったが、挿入ソートは内側のwhileループが後ろから前に向かって走査する点が最大の違いである。

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

3回目のパス（i=3）に注目する。この時点で配列は 2 5 8 1 9 3、key = arr[3] = 1 である。

key = arr[3] の時点で key という変数に1を退避した後、配列自体の arr[3] はまだ書き換えられていない。そこに arr[3] = arr[2]（8をコピー）を実行するので、この瞬間は

• arr[2] = 8（元の値、まだ上書きされていない）
• arr[3] = 8（コピーされた値）

という一時的な重複が発生する。key変数に退避した1は、ループが終わるまで配列のどこにも書き戻されないので、シフトのたびに配列上は同じ値が2箇所に存在する状態になるのである。

whileループを抜けた時点で j+1 = 0 となり、その位置にkey(1)を挿入する。結果として 1 2 5 8 9 3 となる。

この「シフトと挿入は別処理」という構造が、トレース問題では狙われやすい。シフトのたびに値が上書きされていくため、途中経過の配列を答えさせる設問では、shiftが起きた回数だけ同じ値が2箇所に一時的に存在する状態を正しく追えるかが問われる。

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

1. 外側ループが「これから挿入する値の位置」、内側ループが「挿入先を探しながら値をずらす処理」を表していることをまず押さえる
2. whileループの条件（arr[j] > key）が偽になった時点、またはj<0になった時点でループが止まることを確認する。止まった直後のj+1が挿入位置である
3. keyという「退避用の変数」が出てきたら、ループ中に上書きされないよう最初に確保された値だと読み取る
4. 穴埋め問題では、シフトが起きるたびに配列の同じ値が2箇所に重複して見える一時的な状態に惑わされず、最終的な挿入位置を先に特定してから配列を埋めるとよい

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

配列サイズをnとすると、最悪計算量（データが降順に並んでいる場合）はバブルソート・選択ソートと同じくO(n²)である。一方で、データがほぼ整列済みの場合はシフトがほとんど発生せず、最良計算量はO(n)まで下がる。

ここがバブルソート・選択ソートとの比較で問われやすいポイントである。選択ソートは並び方に関わらず常にO(n²)だが、挿入ソートは入力データの状態によって計算量が変化するという性質を持つ。

まとめ

• 挿入ソートは、外側ループで挿入する値を決め、内側ループで挿入位置を探しながら値をずらすという構造である
• バブルソート・選択ソートとは走査の向き（後ろから前）が逆である点が特徴的
• ほぼ整列済みのデータに対しては最良計算量O(n)になる点が、他の2つのソートとの比較で頻出

これでバブル・選択・挿入という基本的なO(n²)ソート3種のトレース問題対応が一区切りとなる。次回以降は、この3つをまとめて比較したり、選択・挿入ソートをGO/kotlinに移植したり、他のアルゴリズムを取り上げていく予定である。

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