目次から探す
挿入ソートとは
挿入ソートは、要素を適切な位置に挿入していくことで配列をソートするアルゴリズムです。
具体的には、先頭の要素をソート済みとみなし、次の要素を適切な位置に挿入していきます。
この操作を配列の最後の要素まで繰り返すことで、全体がソートされた配列が得られます。
挿入ソートの計算量
挿入ソートの計算量は、ソートする配列の要素数に依存します。
以下に挿入ソートの計算量を示します。
| ケース | 計算量 | 説明 |
|---|---|---|
| 最良の場合 | 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 となります。