単純挿入ソートとは
単純挿入ソートのアルゴリズムについて解説します。
一番端から順番に既にソートされているものとし、次の値をソートされている列の所定の位置に挿入していきます。
以下の配列を例に挙げ、実際にみていきましょう。
添え字 | [0] | [1] | [2] | [3] | [4] |
値 | 4 | 2 | 9 | 6 | 0 |
0番目の4を既にソートされているものとし、次の2をソート済みの列の後ろから順に比較していきます。
一番後ろの4より小さいので並べ変えます。
添え字 | [0] | [1] | [2] | [3] | [4] |
値 | 2 | 4 | 9 | 6 | 0 |
次に9を比較すると4より大きいので位置は変わりません。
添え字 | [0] | [1] | [2] | [3] | [4] |
値 | 2 | 4 | 9 | 6 | 0 |
以下同様に入れ替えていきます。
添え字 | [0] | [1] | [2] | [3] | [4] |
値 | 2 | 4 | 6 | 9 | 0 |
添え字 | [0] | [1] | [2] | [3] | [4] |
値 | 2 | 4 | 6 | 9 | 0 |
添え字 | [0] | [1] | [2] | [3] | [4] |
値 | 2 | 4 | 6 | 0 | 9 |
添え字 | [0] | [1] | [2] | [3] | [4] |
値 | 2 | 4 | 0 | 6 | 9 |
添え字 | [0] | [1] | [2] | [3] | [4] |
値 | 2 | 0 | 4 | 6 | 9 |
添え字 | [0] | [1] | [2] | [3] | [4] |
値 | 0 | 2 | 4 | 6 | 9 |
これでソートは完了です。
ソースコード
以下がソースコードです。
insertsort_sample.c
#include <stdio.h> void show_array(int a[], int len) { int i; for (i = 0; i < len; i++) printf("%d ", a[i]); printf("\n"); } int main(void) { int arr[] = { 5, 2, 6, 1, 3, 9 , 3, 7, 4, 0}; int arr_len = 10; //配列の長さ int i, j, temp; for (i = 1; i < arr_len; i++) { temp = arr[i]; for (j = i; j > 0 && arr[j - 1] > temp; j--) arr[j] = arr[j - 1]; arr[j] = temp; show_array(arr, arr_len); } return 0; }
このコードでは挿入する値をtempに保存しておき、arr[j]が挿入する値よりも大きければ一つずつ位置をずらしています。
その後、所定の位置までずらしたら空いたところにtempを挿入しています。