挿入ソートとは

今回は人間にとって大変分かりやすいアルゴリズムです。まず、配列の最初の2つを取り出してソートします。次に、3つ目の値をソート済みした2つの値と順番に比較して、適切な位置に挿入します。以降も同様にソート済みの配列の適切な位置に新しい値を挿入していくだけです。

とかいう説明をするとややこしいですが、トランプの大富豪なんかをやる時に、配られた手札を並び替えますよね。多くの人は挿入ソートアルゴリズムによって並び替えると思います。

例えば、4, 3, 10, 7, 8 という5枚の手札が配られたとします (大人数ですね)。まず、左の 3 と 4 を入れ替えます。

3, 4, 10, 7, 8

次は、10 ですがソート済みの 3 と 4 と比べると今の順序で問題ないのでパスします。まあ、私の場合ここで 10 を右端に持ってきますが。次に 7 を見ると、4 と 10 の間の数値なので、その場所に挿入します。

3, 4, 7, 10, 8

最後は右端の8です。ソート済みの4枚を見ると、 7 と 10 の間なので、その場所に挿入します。

3, 4, 7, 8, 10

これが、挿入ソートアルゴリズムです。

#include <stdio.h>
#define swap(x, y) { (x != y) && (x += y, y = x - y, x -= y); }

void insertion_sort(int *, int);
void show(int *, int);

// ソート前のデータを表示後、ソートしてからソート後のデータを表示する
int main(void) {
    // ソートするデータの情報
    const int count = 5;
    int data[] = { 3, 2, 5, 1, 4 };

    // ソート前のデータを表示
    printf("ソート前：");
    show(data, count);

    // ソート実行
    insertion_sort(data, count);
    
    // ソート後のデータを表示
    printf("ソート後：");
    show(data, count);

    return (0);
}

// data[] を順に表示する
void show(int data[], int count) {
    int i;
    for (i = 0; i < count; i++) printf("%d, ", data[i]);
    printf("\n");
}

// 挿入ソート関数
void insertion_sort(int data[], int count) {
    int i, j, temp;

    for (i = 1; i < count; i++) {
        j = i;

        while ((j > 0) && (data[j - 1] > data[j])) {
            swap(data[j - 1], data[j]);
            j--;
        }
    }
}

実行結果

ソート前：3, 2, 5, 1, 4,
ソート後：1, 2, 3, 4, 5,

ソート関数の解説

void insertion_sort(int data[], int count) {
    int i, j, temp;

    for (i = 1; i < count; i++) {
        j = i;

        while ((j > 0) && (data[j - 1] > data[j])) {
            swap(data[j - 1], data[j]);
            j--;
        }
    }
}

変数i のループで2つ目から最後まで順に処理していきます。処理の内容は、ソート済みの配列に対して適切な位置までスワップを繰り返しています。適切な位置までスワップを繰り返すということは、ソート前のデータが既に整列されていればされているほど、比較回数も交換回数も少なくて済むので高速だということです。

つまり、配列の要素数を n としたとき、最悪計算時間は O(n²) なのに対して、最良計算時間は O(n) となります。また、データが連結リストで格納されている場合は、スワップを繰り返す擬似的挿入ではなく、文字通りの”挿入”を行うことができるため、交換回数を大幅に減少することができます。