C++における挿入ソートの時間計算量をわかりやすく解説

挿入ソートの時間計算量とは？

時間計算量とは、入力データの量を関数としたときに、一連のコードやアルゴリズムが処理・実行されるのにかかる時間のことを指します。

挿入ソートの場合、最良ケースでは O(n)（ビッグオー・オブ・エヌ）のオーダーになります。一方、平均ケースおよび最悪ケースでは O(n²) のオーダーとなります。

配列 6, 5, 8, 7, 10, 9 …（i と i-1 が入れ替わった形）に挿入ソートを適用した場合の時間計算量は？

このような配列をソートする場合の時間計算量は O(n) です。この配列を詳しく観察すると、隣接する要素同士のペアがすべて元の位置から入れ替わっていることがわかります。つまり、1番目と2番目の要素が入れ替わり、3番目と4番目の要素が入れ替わり、以降も同様のパターンが続いています。そのため、ソート処理では各要素に対してわずか1回の操作を n 回繰り返すだけで整列が完了します。

挿入ソートの定義と実装コード

挿入ソートとは、ソート済みの配列の中で各要素を適切な位置へ挿入していくことで、データ構造全体を整列させるソートアルゴリズムです。

以下のコードは、挿入ソートの関数を実装したものです。

サンプルコード

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++){
        int element = arr[i];
        int j = i-1;
        while (j >= 0 && arr[j] > element){
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = element;
    }
}

この実装では、配列の2番目の要素から順に取り出し、それより前のソート済み部分と比較しながら適切な位置へ挿入していきます。外側のループが n 回、内側の while ループが要素の移動回数に応じて実行されるため、入力データの並び方によって計算量が O(n) から O(n²) まで変化します。