【図解】挿入ソート：アルゴリズム【C言語】

本記事では、基本的なソートの一種である「挿入ソート」のアルゴリズム解説・C言語による実装を確認していきます。

アルゴリズム解説では、図を用いた解説を行うため、イメージしやすい構成となっています。

ソートは、アルゴリズムの中でも非常に基本的な分野なので、是非この機会にマスターしましょう。

本記事でわかること

挿入ソートの基本的な情報
アルゴリズムの流れ
C言語による実装方法

こちらの記事で、他のソートアルゴリズムをまとめています。

>>ソートアルゴリズム　計算量・特徴一覧

アルゴリズム入門書はこの一冊で十分！

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

created by Rinker

¥3,938 （2020/09/01現在 Amazon調べ・詳細）

1 挿入ソートとは
2 挿入ソートのアルゴリズム
3 挿入ソートの実装【C言語】

挿入ソートとは

挿入ソートは、ソートアルゴリズムの一種であり、比較的簡単なソートです。

基本的な情報は以下になります。

最悪計算時間 \(O\)	安定性
\(O(n^2)\)	安定

挿入ソートは、その名の通り１つ１つの値を適切な箇所に挿入していくことで、全体をソートするアルゴリズムです。

また、バブルソートや選択ソートと同じく、左端から徐々にソート済み部分が増えていくアルゴリズムとなっています。

>>【図解】バブルソート：アルゴリズム【C言語】

>>【図解】選択ソート：アルゴリズム【C言語】

次の章で具体的な動きを確認していきます。

挿入ソートのアルゴリズム

まずは、軽く全体的な流れを確認し、その後、図を用いた説明へと移ります。

挿入ソートのアルゴリズムは以下のようになります。

始めに、先頭の要素をソート済み部分とする
未ソート部分が無くなるまで、以下の処理を繰り返す
1. 未ソート部分の先頭要素を、変数\(v\)に格納する
2. ソート済み部分において、\(v\)よりも大きい要素を後方へ１つずつずらす
3. 最後に空いた位置に\(v\)を挿入する

文面だと伝わりづらいので、さっそく実例を見ていきましょう。

今回は、サイズが８の配列で昇順ソートの具体例を見ていきます。

ここでは、配列の初期状態を次のようにします。

初期状態では、すべての要素が未ソート部分となりますね。

では、上で確認したアルゴリズム通りに動かしていきます。

まずは、先頭要素である「８」をソート済み部分にします。

次に、未ソート部分の先頭要素「３」を、変数\(v\)に格納します。

格納した後、ソート済み部分の中で「３」よりも大きな値を右へ１つずつ移動していきます。

１つ後ろへずらす際、もともとあった値は上書きします。

最後に空いた位置に、\(v\)に格納していた「３」を挿入します。

これで、左側の２つの要素がソート済みとなりました。

後は、ここまでの動作を繰り返していきます。

もう１セット確認していきましょう。

まずは、未ソート部分の先頭要素「５」を、変数\(v\)に格納します。

格納した後、ソート済み部分の中で「５」よりも大きな値を右へ１つずつ移動していきます。

そして、最後に空いた位置に、\(v\)に格納していた「５」を挿入します。

これで、左側の3つの要素がソート済みとなりました。

後は、すべての要素が動かなくなるまで、これまでの動作を繰り返していきます。

では、ここまで行ってきた分を２セット分とし、ここからは１セットおきの配列の状態を示していきます。

これで配列の要素すべてがソート済みとなりました。

ここまでが挿入ソートアルゴリズムの動きとなります。

次の章では、これをC言語で実装していきます。

実際に自分の手で実装することで、より理解が深まるので、是非確認してみてください。

挿入ソートの実装【C言語】

さっそく、プログラム全体のコードを示します。

#include <stdio.h>
#define N 8

// 配列の全ての要素を出力する
void printArray(int A[], int n) {
    for (int i = 0; i < n; i++) {
        if (i == 0)
            printf("%d", A[i]);
        else
            printf(" %d", A[i]);
    }
    printf("\n");
}

// 配列の要素を入れ替える
void swap(int A[], int a, int b) {
    int temp;
    temp = A[a];
    A[a] = A[b];
    A[b] = temp;
}

void insertSort(int A[], int n) {
    int i, j, v;
    for (i = 1; i < n; i++) {
        v = A[i];   // 未ソート部分の先頭要素を格納
        j = i - 1;

        // vよりも大きい値を１つずつ移動する
        while (j >= 0 && A[j] > v) {
            A[j+1] = A[j];
            j--;
        }

        A[j+1] = v;   // 最後に空いた位置に挿入
    }
}

int main(void) {
    int A[N] = {8, 3, 5, 1, 7, 4, 2, 6};

    printArray(A, N); // ソート前の配列の要素を表示
    insertSort(A, N); // 挿入ソートを行う
    printArray(A, N); // ソート後の配列の要素を表示
    return 0;
}

#include <stdio.h>

#define N 8

// 配列の全ての要素を出力する

void printArray(int A[], int n) {

for (int i = 0; i < n; i++) {

if (i == 0)

printf("%d", A[i]);

else

printf(" %d", A[i]);

}

printf("\n");

}

// 配列の要素を入れ替える

void swap(int A[], int a, int b) {

int temp;

temp = A[a];

A[a] = A[b];

A[b] = temp;

}

void insertSort(int A[], int n) {

int i, j, v;

for (i = 1; i < n; i++) {

v = A[i]; // 未ソート部分の先頭要素を格納

j = i - 1;

// vよりも大きい値を１つずつ移動する

while (j >= 0 && A[j] > v) {

A[j+1] = A[j];

j--;

}

A[j+1] = v; // 最後に空いた位置に挿入

}

int main(void) {

int A[N] = {8, 3, 5, 1, 7, 4, 2, 6};

printArray(A, N); // ソート前の配列の要素を表示

insertSort(A, N); // 挿入ソートを行う

printArray(A, N); // ソート後の配列の要素を表示

return 0;

}

長々としていますが、挿入ソート本体は、23~37行目の insertSort関数の中で実装しています。

挿入ソートの実装は比較的容易であるため、詳細の解説は割愛します。

insertSort関数のループ内で、配列の要素が交換されるたびに要素を出力するようなコードを書き加えると、前の章で確認したような数値の並びになることが確認できるかと思います。

では、今回はここまでとします。

お疲れさまでした。

別のソートを確認したい方は、ソートアルゴリズム　計算量・特徴一覧をご覧ください。