基本挿入法
比較範囲の限定
挿入ソートとも呼ばれる整列アルゴリズムで、安定的なアルゴリズムです
バブルソートと同様に、配列の初期の並びで処理回数が異なります
このソートのアルゴリズムは、比較範囲を限定して整列していきます
調べる範囲を少しずつ増やしながら、全体を並べていきます
ここで重要なのは、すでに比較した範囲の大小関係は保証されているということです
最初にx[1]とx[0]を比較します
ここでの比較は、必ず１回行われます
次に、カウンターを進めてx[2]とx[1]を比較します
もしここで、x[2]がx[1]よりも大きければ（昇順のとき）なにもせずにカウンターを進めることができます
x[0]とx[1]の関係は、この前のループ時に保証されているからです
もしx[2]とx[1]の関係が逆であれば、それを入れ換えてx[1]とx[0]を比較します
x[1]を入れ換えているので、この関係も保証されなくなっています
もし、全ての要素がソート済みの場合は要素数 n - 1 回の処理回数になります
int * insertionSort(int *ary , int last_index) {
int count1 , count2 , tmp;
for (count1 = 1 ; count1 < last_index ; count1++)
for (count2 = count1 - 1 ; count2 >= 0 && *(ary + count2) > *(ary + count2 + 1); count2--) {
tmp = *(ary + count2 + 1);
*(ary + count2 + 1) = *(ary + count2);
*(ary + count2) = tmp;
}
return ary;
}
第一引数にソートする配列を、第二引数に配列の最大要素を指定します
ネストしたfor文の count2 >= 0 && *(ary + count2) > *(ary + count2 + 1) は
if文に分割してbreakで抜け出す形をとってもかまいません
論理積のショートカットがサポートされていない言語では、上記のループは使えません
（count2 >= 0 が偽でも、論理積はその後を評価しようとする）