挿入ソート

1. 挿入ソートアルゴリズム
2. 挿入ソートの例
3. 挿入ソートアルゴリズムの実装
4. 挿入ソートアルゴリズムの複雑さ

挿入ソートは、単純な比較ベースのソートアルゴリズムです。このアルゴリズムでは、ソートされた部分配列とソートされていない部分配列の 2つの部分配列を保持します。ソートされていない部分配列から 1つの要素が、ソートされた部分配列の中で正しい位置を見つけ、そこに挿入されます。これは、ある人が手に持っているカードの山を並べ替えるのに似ています。これは、正しい位置に要素を挿入するように動作するので、挿入ソートと名付けられています。このアルゴリズムは、小さなデータセットには効率的ですが、大きなデータセットには適していません。

挿入ソートアルゴリズム

n 個の要素を含むソートされていない配列 A[] があると仮定します。最初の要素 A[0] は既にソートされており、ソートされた部分配列の中にあります。

挿入ソートの例

配列 (5,3,4,2,1) があるとします。挿入ソートアルゴリズムを使用してソートします。

• 最初のイテレーション

キー : A[1] = 3

• 2 回目のイテレーション

キー : A[2] = 4

• 3 回目のイテレーション

キー : A[3] = 2

• 4 回目のイテレーション

キー : A[4] = 1

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

#include <iostream>
using namespace std;

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

int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  insertion_sort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

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

時間複雑度

• 平均のケース

平均的には、挿入ソートの ith パスで i の比較が行われる。したがって、n 回の繰り返しがある場合、平均的な時間の複雑さは以下のようになります。

1 + 2 + 3 + ... + (n-1) = n*(n-1)/2

したがって、時間の複雑さは [Big Theta]：O(n²)のオーダーです。

• 最悪のケース

最悪の場合は、配列が逆にソートされたときに発生し、最大数の比較とスワップを実行しなければならません。

最悪の場合の時間的複雑さは [Big O]：O(n²)です。

• 最良のケース

最良のケースは、配列が既にソートされているときに、外側のループだけを n 回実行したときです。

最良の時間的複雑さは [Big Omega]: O(n) です。

空間計算量

挿入ソートアルゴリズムの空間複雑度は、一時変数以外に余分なメモリを必要としないため、O(n) です。