【基本情報技術者試験】挿入ソート問題を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つを一度まとめて比較する記事や他のアルゴリズムを取り上げる予定である。

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