【C言語】挿入ソートの比較回数は何回?他のソートよりも早いのか紹介

目次から探す

挿入ソートとは

挿入ソートは、要素を適切な位置に挿入していくことで配列をソートするアルゴリズムです。

具体的には、先頭の要素をソート済みとみなし、次の要素を適切な位置に挿入していきます。

この操作を配列の最後の要素まで繰り返すことで、全体がソートされた配列が得られます。

挿入ソートの計算量

挿入ソートの計算量は、ソートする配列の要素数に依存します。

以下に挿入ソートの計算量を示します。

ケース計算量説明
最良の場合O(n)ソート済みの配列をソートする場合
最悪の場合O(n^2)逆順にソートされた配列をソートする場合
平均の場合O(n^2)平均的なケースでの比較回数

挿入ソートの実装例

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

#include <stdio.h>
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("ソート結果:");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

上記のコードでは、insertionSort関数を定義しています。

この関数は、挿入ソートを行うための処理を行います。

main関数では、ソートする配列を定義し、insertionSort関数を呼び出しています。

最後に、ソート結果を表示しています。

実行結果は 1 2 5 8 9 となります。

目次から探す