>> C言語入門トップに戻る

挿入ソート

今回は挿入ソートについて説明します。

挿入ソートとは、先頭部分のソート済みである領域に、後ろの要素を適切な場所へ挿入していく方法です。

３

５

８

６

１

例えば、あらかじめ先頭三つの要素がソート済みだったとします。
次にその後ろの要素とソート済みの領域にある要素の後ろの要素から比較し、
適切な場所へ挿入します。
今回の場合は６を、８，５，３と後ろから順番に比較していくわけですから、
５と比較した時点で、６の位置は５の後ろに置くべきだな、と判断できます。
なぜか分かりますよね？既にソート済みなのですから３となんか比較する必要ないからです。
この挿入ソートはあらかじめ、先頭部分の要素がある程度ソート済みである場合と、
後ろの方の要素に、偶然大きい値(小さい値)が多く存在すると速度的には早くなります。

以下のコードを見てください。

#include <stdio.h>

int main(void)
{
	int test[10]={3,10,4,5,6,1,8,7,9,2};

	//配列の要素数を取得
	int number=sizeof(test)/sizeof(int);

	//一時的な領域
	int work;

		//先頭より一つ上の要素からチェック
		for(int s=1;s<number;++s){
			
			//ソート済み部分の要素と比較(以降はバブルソート)
			for(int i=s; i!=0 && test[i]<test[i-1] ;--i){
				//ソート済みなので自分より小さいところがあればそこへ代入するだけ
				work=test[i-1];
				test[i-1]=test[i];
				test[i]=work;
			}
		}

	//並びかえ出来たか確認
	for(int i=0;i<number;++i){
		printf("%d,",test[i]);
	}

	//改行
	puts("");

	return 0;
}

全要素ソート済みでないと仮定して書いています。
ですので、先頭の次の要素からチェックをし、
その要素と一つ下の要素とをバブルソートで比較していってます。
0番目の要素まで比較するか、比較要素の値がソート済みの要素より大きかった時点でループを抜けます。
もし比較要素が、一つ下の要素より大きかった場合はその時点でループが終了するのでより高速になるというわけです。

以上が、挿入ソートの説明になります。


>> 【線形探索】に進む
>> C言語入門トップに戻る