【C言語】挿入ソートの仕組みと実装方法をわかりやすく解説

ソート（整列）とは、データの要素を昇順または降順のいずれかの順序に並べ替える処理のことです。C言語ではさまざまなソートアルゴリズムを実装でき、それぞれ計算量や特性が異なるため、目的に応じた使い分けが重要になります。

C言語で使われる主なソートの種類

C言語でよく利用されるソート手法には、次の5つがあります。

• バブルソート（交換ソート）
• 選択ソート
• 挿入ソート（線形ソート）
• クイックソート（分割交換ソート）
• マージソート（外部ソート）

挿入ソートとは

挿入ソートは、整列済みの部分に新しい要素を適切な位置へ「挿入」していくことで、配列全体を並べ替えるアルゴリズムです。トランプの手札を順番に整理する作業に似ており、考え方が直感的で初心者にも理解しやすいのが特徴です。

挿入ソートで要素を並べ替える際の基本的なロジックは以下の通りです。

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

アルゴリズムの動作解説

まず、並べ替え前のバラバラの状態の要素を用意します。

挿入ソートでは、先頭から2番目の要素を起点として、注目している要素をその左側にある整列済みの部分と順に比較していきます。隣接する要素との大小関係が逆であれば交換を繰り返し、正しい位置に到達した時点でその要素を挿入します。この操作を末尾の要素まで順番に行うことで、配列全体が昇順に整列されます。

計算量の目安

• 平均・最悪計算量：O(n²)
• 最良計算量（ほぼ整列済みのデータ）：O(n)
• 安定ソート：等しい値の前後関係は維持されます

このように、挿入ソートはデータ数が少ない場合や、すでにほぼ整列されているデータに対して高い効力を発揮するシンプルなアルゴリズムです。

C言語による挿入ソートの実装例

以下は、挿入ソートを用いて要素を昇順に並べ替えるC言語プログラムの例です。

#include <stdio.h>
int main() {
    int a[50], i, j, n, t;
    printf("リストの要素数を入力してください：\n");
    scanf("%d", &n);
    printf("要素を入力してください：\n");
    for(i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    for(i = 1; i <= n - 1; i++){ 
        for(j = i; j > 0 && a[j - 1] > a[j]; j--){
            t = a[j];
            a[j] = a[j - 1];
            a[j - 1] = t;
        }
    }
    printf("挿入ソート後の要素は以下の通りです：\n");
    for(i = 0; i < n; i++)
        printf("%d\t", a[i]);
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

リストの要素数を入力してください：
10
要素を入力してください：
34
125
2
6
78
49
1
3
89
23
挿入ソート後の要素は以下の通りです：
1 2 3 6 23 34 49 78 89 125