【C言語】挿入ソートとは？仕組みや実装方法をコード付きで解説

2023-09-102024-07-23

この記事では、C言語の基本的なソートアルゴリズムの一つである「挿入ソート」について学びます。

挿入ソートの基本概念や特徴、具体的な仕組み、実装方法、性能、応用例、そしてメリットとデメリットについて詳しく解説します。

プログラミング初心者でも理解しやすいように、サンプルコードや実行結果を交えながら説明していきますので、ぜひ最後まで読んでみてください。

目次から探す

挿入ソートの基本概念

挿入ソートとは

挿入ソート(Insertion Sort)は、ソートアルゴリズムの一つで、データの集合を整列するための手法です。

挿入ソートは、カードゲームの手札を整列する方法に似ています。

具体的には、未整列のデータを一つずつ取り出し、既に整列された部分に適切な位置に挿入していくことで、全体を整列させます。

挿入ソートの特徴

挿入ソートには以下のような特徴があります。

シンプルなアルゴリズム: 挿入ソートは非常にシンプルで理解しやすいアルゴリズムです。

そのため、プログラミング初心者にも適しています。

安定ソート: 同じ値の要素の順序が保持されるため、安定ソートと呼ばれます。
内部ソート: データを追加のメモリを使わずにソートするため、内部ソートに分類されます。
小規模データに適している: データの数が少ない場合や、部分的に整列されたデータに対しては非常に効率的です。

安定ソートである

挿入ソートは安定ソートです。

安定ソートとは、同じ値の要素が元の順序を保つソートアルゴリズムのことを指します。

例えば、データに同じ値が複数存在する場合、挿入ソートではそれらの順序が変わりません。

これは、特定の条件下でデータの順序を保持したい場合に有用です。

内部ソートである

挿入ソートは内部ソートに分類されます。

内部ソートとは、ソートの過程で追加のメモリをほとんど使用しないソートアルゴリズムのことです。

挿入ソートでは、データをその場で並べ替えるため、追加のメモリを必要としません。

この特性により、メモリ効率が良いソートアルゴリズムと言えます。

適用範囲

挿入ソートは以下のような状況で特に有効です。

小規模データのソート: データの数が少ない場合、挿入ソートは非常に効率的です。

データが少ないと、他の複雑なソートアルゴリズムよりも高速に動作することがあります。

部分的に整列されたデータのソート: 既に部分的に整列されているデータに対しては、挿入ソートは非常に効率的です。

例えば、ほとんど整列されているデータに対しては、挿入ソートはほぼ線形時間で動作します。

リアルタイムシステムでの利用: 挿入ソートはシンプルで実装が容易なため、リアルタイムシステムや組み込みシステムでの利用に適しています。

挿入ソートはそのシンプルさと効率性から、特定の状況で非常に有用なソートアルゴリズムです。

次のセクションでは、挿入ソートの仕組みについて詳しく解説します。

挿入ソートの仕組み

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

挿入ソートは、配列の要素を一つずつ取り出し、それを適切な位置に挿入することで配列を整列させるアルゴリズムです。

この方法は、手持ちのカードを並べ替える際に使う方法に似ています。

具体的には、未整列の部分から要素を一つ取り出し、既に整列された部分に挿入していくという手順を繰り返します。

アルゴリズムの流れ

配列の最初の要素は既に整列されているとみなす。
次の要素を取り出し、既に整列された部分の適切な位置に挿入する。
この操作を配列の最後の要素まで繰り返す。

擬似コードでの説明

以下に挿入ソートの擬似コードを示します。

for i from 1 to length(A) - 1
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key
        A[j + 1] = A[j]
        j = j - 1
    A[j + 1] = key

この擬似コードでは、Aはソート対象の配列、keyは現在挿入しようとしている要素、iとjはインデックスを示しています。

挿入ソートの動作例

具体的な例を用いて挿入ソートの動作を説明します。

以下の配列をソートする場合を考えます。

[5, 2, 4, 6, 1, 3]

最初の要素 5 は既に整列されているとみなします。
次に 2 を取り出し、5 の前に挿入します。 ` [2, 5, 4, 6, 1, 3]

[2, 5, 4, 6, 1, 3]

次に 4 を取り出し、5 の前に挿入します。

[2, 4, 5, 6, 1, 3]

次に 6 を取り出し、既に整列された部分に適切な位置に挿入します。

[2, 4, 5, 6, 1, 3]

次に 1 を取り出し、適切な位置に挿入します。 `


[1, 2, 4, 5, 6, 3]

最後に 3 を取り出し、適切な位置に挿入します。

[1, 2, 3, 4, 5, 6]

具体的な例での説明

以下に、具体的なC言語のコードを示します。

このコードは、上記のアルゴリズムを実装したものです。

#include <stdio.h>
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // arr[j] > key の場合、arr[j] を arr[j + 1] に移動
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printArray(arr, n);
    return 0;
}

このコードを実行すると、以下のような結果が得られます。

1 2 3 4 5 6

ステップごとの動作

上記のコードをステップごとに解説します。

insertionSort 関数が呼び出され、配列 arr とその長さ n が渡されます。
外側の for ループは、配列の2番目の要素から最後の要素までを順に処理します。
key に現在の要素を格納し、j にその前の要素のインデックスを設定します。
内側の while ループは、key より大きい要素を右にシフトします。
while ループが終了したら、key を適切な位置に挿入します。
最後に、printArray 関数でソートされた配列を表示します。

このようにして、挿入ソートは配列を一つ一つの要素を適切な位置に挿入することで整列させます。

挿入ソートの実装方法

挿入ソートの実装方法について、具体的なC言語のコードを用いて解説します。

挿入ソートは比較的シンプルなアルゴリズムであり、初心者でも理解しやすいです。

以下に、挿入ソートの基本的な実装例を示します。

基本的な挿入ソートの実装

まずは、基本的な挿入ソートの実装を見てみましょう。

#include <stdio.h>
// 挿入ソートを実行する関数
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // keyより大きい要素を一つ後ろにシフト
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
// 配列を表示する関数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("ソート前の配列: \n");
    printArray(arr, n);
    insertionSort(arr, n);
    printf("ソート後の配列: \n");
    printArray(arr, n);
    return 0;
}

コードの解説

insertionSort関数:

arr[]はソート対象の配列、nは配列の要素数です。
外側のforループは配列の2番目の要素から始まり、最後の要素まで繰り返します。
keyは現在の要素を保持し、jはその前の要素のインデックスです。
内側のwhileループは、keyより大きい要素を一つ後ろにシフトします。
whileループが終了したら、keyを正しい位置に挿入します。

printArray関数:

配列の要素を順番に表示するための関数です。

main関数:

ソート対象の配列を定義し、ソート前とソート後の配列を表示します。

実行結果

このプログラムを実行すると、以下のような結果が得られます。

ソート前の配列: 
12 11 13 5 6 
ソート後の配列: 
5 6 11 12 13

挿入ソートのポイント

シンプルな実装: 挿入ソートは非常にシンプルで、理解しやすいアルゴリズムです。
小規模データに強い: 小規模なデータセットに対しては非常に効率的です。
安定ソート: 同じ値の要素の順序が保持されるため、安定ソートと呼ばれます。

挿入ソートは、特に小規模なデータや部分的に整列されたデータに対して有効です。

次に、挿入ソートの性能について詳しく見ていきましょう。

挿入ソートの性能

時間計算量

挿入ソートの時間計算量は、データの並び方によって異なります。

時間計算量は、アルゴリズムがデータを処理するのにかかる時間を示す指標で、通常は入力データのサイズに対する関数として表されます。

最良計算量

最良計算量は、データが既に整列されている場合の計算量です。

挿入ソートでは、各要素が既に正しい位置にあるため、比較と挿入の操作が最小限で済みます。

この場合、時間計算量は O(n) となります。

ここで n はデータの要素数です。

平均計算量

平均計算量は、データがランダムに並んでいる場合の計算量です。

挿入ソートでは、各要素を適切な位置に挿入するために、平均してリストの半分の要素と比較する必要があります。

このため、平均計算量は O(n^2) となります。

最悪計算量

最悪計算量は、データが逆順に並んでいる場合の計算量です。

この場合、各要素を挿入するために、リストの全ての要素と比較する必要があります。

したがって、最悪計算量も O(n^2) となります。

空間計算量

挿入ソートは、入力データをその場で並べ替える「インプレース」アルゴリズムです。

追加のメモリをほとんど必要としないため、空間計算量は O(1) です。

これは、データのサイズに関係なく一定のメモリしか使用しないことを意味します。

他のソートアルゴリズムとの比較

バブルソートとの比較

バブルソートも O(n^2) の時間計算量を持つ単純なソートアルゴリズムです。

しかし、挿入ソートはバブルソートよりも実際のパフォーマンスが良いことが多いです。

これは、挿入ソートがデータの一部が既に整列されている場合に効率的に動作するためです。

クイックソートとの比較

クイックソートは、平均計算量が O(n log n) であり、挿入ソートよりも高速です。

しかし、クイックソートは最悪計算量が O(n^2) となる場合があります。

挿入ソートは小規模なデータセットや部分的に整列されたデータに対しては有効ですが、大規模なデータセットにはクイックソートの方が適しています。

以上のように、挿入ソートは特定の状況下で非常に有効なソートアルゴリズムですが、データの規模や特性に応じて他のソートアルゴリズムと使い分けることが重要です。

挿入ソートの応用例

挿入ソートは、そのシンプルなアルゴリズムと効率性から、特定の状況で非常に有用です。

以下に、挿入ソートが特に効果的に機能するいくつかの応用例を紹介します。

小規模データのソート

挿入ソートは、小規模なデータセットのソートに非常に適しています。

データの数が少ない場合、他の複雑なソートアルゴリズムを使用するよりも、挿入ソートの方が実装が簡単で、実行時間も短くなることが多いです。

例えば、以下のような小規模データセットを挿入ソートでソートする場合を考えてみましょう。

#include <stdio.h>
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // keyより大きい要素を一つ後ろに移動
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printArray(arr, n);
    return 0;
}

このコードは、5つの要素からなる配列を挿入ソートでソートします。

実行結果は以下の通りです。

5 6 11 12 13

部分的に整列されたデータのソート

挿入ソートは、部分的に整列されたデータのソートにも非常に効果的です。

例えば、ほとんどの要素が既に整列されている場合、挿入ソートは非常に高速に動作します。

これは、挿入ソートが最良計算量でO(n)の時間計算量を持つためです。

以下に、部分的に整列されたデータを挿入ソートでソートする例を示します。

#include <stdio.h>
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr[] = {1, 2, 3, 5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printArray(arr, n);
    return 0;
}

このコードは、ほとんど整列されているが一部だけ順序が乱れている配列をソートします。

実行結果は以下の通りです。

1 2 3 4 5

リアルタイムシステムでの利用

挿入ソートは、リアルタイムシステムでも利用されることがあります。

リアルタイムシステムでは、データが逐次的に入力されることが多く、その都度データをソートする必要があります。

挿入ソートは、データが追加されるたびに効率的にソートを行うことができるため、このようなシステムに適しています。

例えば、センサーからのデータがリアルタイムで入力されるシステムを考えてみましょう。

新しいデータが追加されるたびに、既存のデータと比較して適切な位置に挿入することで、常にソートされた状態を保つことができます。

以下に、リアルタイムでデータをソートする例を示します。

#include <stdio.h>
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr[100];
    int n = 0;
    int new_data;
    while (scanf("%d", &new_data) != EOF) {
        arr[n] = new_data;
        n++;
        insertionSort(arr, n);
        printArray(arr, n);
    }
    return 0;
}

このコードは、標準入力からデータを逐次的に受け取り、リアルタイムでソートを行います。

新しいデータが入力されるたびに、ソートされた配列が出力されます。

以上のように、挿入ソートは特定の状況で非常に有用なソートアルゴリズムです。

小規模データのソートや部分的に整列されたデータのソート、リアルタイムシステムでの利用など、さまざまな応用例があります。

挿入ソートのメリットとデメリット

メリット

簡単に実装できる

挿入ソートの最大のメリットは、そのシンプルさにあります。

アルゴリズム自体が直感的で理解しやすく、実装も非常に簡単です。

以下に示すC言語のサンプルコードを見てもわかるように、基本的なループと条件分岐を使うだけで実装できます。

#include <stdio.h>
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // arr[j] > key の場合、arr[j] を arr[j + 1] に移動
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

このコードは、配列 arr を挿入ソートでソートする簡単な例です。

初心者でも理解しやすい構造になっています。