目次から探す
挿入ソートの実装方法
挿入ソートは、配列の要素を順番に取り出し、適切な位置に挿入していくことで配列を昇順に並び替えるアルゴリズムです。
以下では、挿入ソートの2つの実装方法について解説します。
配列の要素を1つずつ挿入していく方法
この実装方法では、配列の要素を1つずつ取り出し、それを適切な位置に挿入していきます。
具体的な手順は以下の通りです。
- 最初の要素をソート済みとみなし、2番目の要素から順に処理を行います。
- 挿入する要素を選びます。
- 挿入する要素を、ソート済みの部分の適切な位置に挿入します。
挿入する位置は、ソート済みの部分を後ろから見ていき、挿入する要素よりも大きい要素が現れた位置です。
- 挿入した要素の後ろにある要素を1つずつ後ろにずらします。
- 挿入する要素を適切な位置に挿入したら、次の要素に移ります。
- 全ての要素を処理し終えたら、配列は昇順に並び替えられます。
配列の要素を一度に挿入していく方法
この実装方法では、配列の要素を一度に挿入していきます。
具体的な手順は以下の通りです。
- 最初の要素をソート済みとみなし、2番目の要素から順に処理を行います。
- 挿入する要素を選びます。
- 挿入する要素を、ソート済みの部分の適切な位置に挿入します。
挿入する位置は、ソート済みの部分を後ろから見ていき、挿入する要素よりも大きい要素が現れた位置です。
- 挿入する要素よりも大きい要素を、一度に1つずつ後ろにずらします。
- 挿入する要素を適切な位置に挿入したら、次の要素に移ります。
- 全ての要素を処理し終えたら、配列は昇順に並び替えられます。
配列の要素を昇順に並び替える
挿入ソートは、配列の要素を昇順に並び替えるための効果的なアルゴリズムです。
挿入ソートはシンプルで理解しやすいため、プログラミング初心者にもおすすめです。
以下に、挿入ソートの実装例を示します。
#include <stdio.h>
void insertionSort(int arr[], int n) {
int i, j, key;
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, 3, 1};
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 3 5 8以上が、挿入ソートを使って配列を昇順に並び替える方法の解説です。
挿入ソートは基本的なソートアルゴリズムの一つであり、他のソートアルゴリズムの理解の基礎となる重要な概念です。
ぜひ、実際にプログラムを書いて挿入ソートを試してみてください。