挿入ソートの基本概念

C言語における挿入ソート（Insertion Sort）は、小規模なデータや部分的に整列済みのデータに対して高い効率を発揮する整列アルゴリズムである。未整列の要素を順番に取り出し、既に整列済みの領域内で適切な挿入位置を後方から探索して挿入することで、全体の順序を構築していく仕組みを持つ。

標準的な挿入ソートの実装

以下に、挿入ソートの基本的な実装例を示す。変数名やループ構造を変更し、ロジックの意図を明確にしている。

#include <stdio.h>

// 挿入ソートの実行関数
void exec_insertion_sort(int dataset[], int element_count) {
    for (int idx = 1; idx < element_count; ++idx) {
        int target_val = dataset[idx];
        int scan_pos = idx - 1;

        // 整列済み領域において、対象値よりも大きい要素を後方にずらす
        while (scan_pos >= 0 && dataset[scan_pos] > target_val) {
            dataset[scan_pos + 1] = dataset[scan_pos];
            scan_pos--;
        }
        // 確保した空き位置に対象値を挿入
        dataset[scan_pos + 1] = target_val;
    }
}

// 配列の内容を出力するヘルパー関数
void display_array(int dataset[], int element_count) {
    for (int i = 0; i < element_count; ++i) {
        printf("%d ", dataset[i]);
    }
    printf("\n");
}

int main(void) {
    int values[] = {42, 17, 55, 3, 29};
    int count = sizeof(values) / sizeof(values[0]);

    display_array(values, count);
    exec_insertion_sort(values, count);
    display_array(values, count);

    return 0;
}

実装のポイント

• ソート関数 exec_insertion_sort：外側のループで未整列要素を先頭から順に選択し、target_valとして保持する。内側のループでは整列済み領域を後方から走査し、値のシフトによって挿入位置を確保してから対象値を格納する。これにより、無駄なスワップ操作を回避している。
• 出力関数 display_array：配列の全要素を走査し、標準出力へ表示する。
• エントリポイント main：テスト用の配列を定義し、ソート前後の状態を出力して動作を確認する。

アルゴリズムの最適化

基本的な挿入ソートにおいて、挿入位置の探索には線形探索が用いられるため、比較回数が増大する。この探索処理を二分探索に置き換えることで、比較のコストを削減できる（二分挿入ソート）。

// 挿入位置を二分探索で特定する関数
int find_insert_pos(int dataset[], int val, int left, int right) {
    if (right <= left) {
        return (val > dataset[left]) ? (left + 1) : left;
    }

    int center = left + (right - left) / 2;

    if (val == dataset[center]) {
        return center + 1;
    }

    if (val > dataset[center]) {
        return find_insert_pos(dataset, val, center + 1, right);
    }
    return find_insert_pos(dataset, val, left, center - 1);
}

// 二分挿入ソートの実行関数
void exec_binary_insertion_sort(int dataset[], int element_count) {
    for (int idx = 1; idx < element_count; ++idx) {
        int target_val = dataset[idx];
        int scan_pos = idx - 1;

        // 二分探索で挿入ポイントを算出
        int insert_location = find_insert_pos(dataset, target_val, 0, scan_pos);

        // 挿入位置までの要素を後方にシフト
        while (scan_pos >= insert_location) {
            dataset[scan_pos + 1] = dataset[scan_pos];
            scan_pos--;
        }

        // 対象値を指定位置に挿入
        dataset[insert_location] = target_val;
    }
}

計算量と安定性の評価

最悪時間計算量は O(n^2) であり、逆順に整列されたデータを処理する際に顕著な性能低下が見られる。しかし、データが完全に整列済みの最良ケースでは O(n) となるため、ほぼ整列済みのデータに対しては極めて高速に動作する。

追加のメモリ領域として定数サイズの変数しか使用しないため、空間計算量は O(1) である。また、等値な要素の相対的な順序が入れ替わらないため、安定なソートアルゴリズムとして分類される。

適用が推奨されるユースケース

• 小規模なデータセット：オーバーヘッドが少なく、シンプルな実装であるため、少量のデータ処理に適している。
• ほぼ整列済みのデータ：既存の順序関係を活かせるため、データの追加や微修正が行われた後の再ソートなどで高い効率を発揮する。
• ストリーミングデータ：データが随時到着する環境において、到着順に適切な位置へ挿入できるオンラインアルゴリズムとして機能する。