C++で挿入ソートを実装する方法｜アルゴリズムとサンプルコードを徹底解説

挿入ソートは、トランプの手札を並べ替えるときの動きに似ているソートアルゴリズムです。カードを整理するときと同じように、データセットから1つの要素を取り出し、その要素を挿入できる適切な位置を作るために他の要素をずらしてから、元の位置に戻すという手順を繰り返します。

挿入ソートの計算量

• 時間計算量：最良ケースは O(n)、平均ケースおよび最悪ケースは O(n²)

• 空間計算量：O(1)

入力 − ソート前のリスト：9 45 23 71 80 55
出力 − ソート後の配列：9 23 45 55 71 80

アルゴリズム

insertionSort(array, size)

入力：データの配列と、配列内の要素の総数

出力：ソート済みの配列

Begin
   for i := 1 to size-1 do
      key := array[i]
      j := i
      while j > 0 AND array[j-1] > key do
         array[j] := array[j-1];
         j := j – 1
      done
      array[j] := key
   done
End

C++による実装例

以下は、挿入ソートをC++で実装したサンプルコードです。ユーザーから要素数と各要素を受け取り、ソート前後の配列を表示します。

#include<iostream>
using namespace std;
void display(int *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}
void insertionSort(int *array, int size) {
    int key, j;
    for(int i = 1; i<size; i++) {
        key = array[i];//値を取り出す
        j = i;
        while(j > 0 && array[j-1]>key) {
            array[j] = array[j-1];
            j--;
        }
        array[j] = key;  //適切な位置に挿入
    }
}
int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];    //指定された要素数で配列を作成
    cout << "Enter elements:" << endl;
    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    insertionSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 6
Enter elements:
9 45 23 71 80 55
Array before Sorting: 9 45 23 71 80 55
Array after Sorting: 9 23 45 55 71 80

このように、挿入ソートは実装がシンプルで、小規模なデータやほぼ整列済みのデータに対しては効率的に動作します。一方で、最悪ケースでは O(n²) の計算量となるため、大規模なデータセットにはクイックソートやマージソートなどの方が適しています。