基本挿入法


比較範囲の限定

挿入ソートとも呼ばれる整列アルゴリズムで、安定的なアルゴリズムです
バブルソートと同様に、配列の初期の並びで処理回数が異なります

このソートのアルゴリズムは、比較範囲を限定して整列していきます
調べる範囲を少しずつ増やしながら、全体を並べていきます
ここで重要なのは、すでに比較した範囲の大小関係は保証されているということです

最初にx[1]とx[0]を比較します
ここでの比較は、必ず1回行われます
次に、カウンターを進めて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 が偽でも、論理積はその後を評価しようとする)



前のページへ戻る次のページへ