整列 ―挿入ソート―

挿入ソートとは

前述の２つの整列と同様に，次の整数値の配列データを昇順に並べ替えてみましょう．

a[0]	a[1]	a[2]	a[3]	a[4]
32	12	24	8	17

挿入ソートは，もう一つ配列を用意すると理解しやすくなります．

b[0]	b[1]	b[2]	b[3]	b[4]

次の手順で，配列 a[0] ～ a[4] のデータを配列 b[0] ～ b[4] へ昇順に並べていきます．

１　前提の処理として a[0] の 32 を，b[0] に入れます．

a	32	12	24	8	17
b	32

２　初めに a[1] の 12 を，b[0] と比較して 32 より小さければ b の 32 の左側に，32 より大きければ b の 32 の右側に，それぞれ挿入します．
この場合は，12 の方が小さいので 32 の左側に挿入します．

a	32	12	24	8	17
b	12	32

３　次に a[2] の 24 を b のデータと比較して，12 と 32 の間に挿入します．

a	32	12	24	8	17
b	12	24	32

４　続いて a[3] の 8 を b のデータと比較して，b の 12 の左側に挿入します．

a	32	12	24	8	17
b	8	12	24	32

５　さらに a[4] の 17 を b のデータと比較して，b の 12 と 32 の間に挿入します．

a	32	12	24	8	17
b	8	12	17	24	32

以上で昇順の整列が完了しました．
バブルソートや選択ソートに比較すると，分かりやすいアルゴリズムです．
ただし，それが cording のしやすさに繋がるかと言うと，一概にそうとは言えません．

Cording

バブルソート・選択ソートと同様に，整数値データを10個与えて昇順に並べるプログラムを作ります．

上のようなものになります．
ところが実際には，新たな配列 b を作ることは，分かりやすくなるもの効率が悪いものです．
配列 a のみを用いた方がシンプルな coding になりますので，下にその一例を載せます．

#include <stdio.h>

int main(void) {
    int a[] = {100, 53, 19, 8, 81, 37, 16, 25, 44, 22};
    int len = sizeof(a) / sizeof(int);

    for (int i = 1; i < len; i++) {
        int j = 0;
        int k = i;
        while (j < i && a[i] > a[j]) {
            j++;
        }
        if (j < i) {
            int b = a[i];
            while (k-- > j + 1) {
                a[k + 1] = a[k];
            };
            a[j] = b;
        }
    }

    for (int i = 0; i < len; i++) {
        printf("%d, ", a[i]);
    }
    printf("\n");

    return 0;
}