C言語による挿入ソートの実装

サンプルプログラム

ここでは実際に、C言語による挿入ソートの実装を見てみることにします。以下のプログラムを実行してみてください。

listex5-select-1 
#include <stdio.h>
 
#define MAX_LENGTH	5

void showData(int*,int);

void main(){
	int array[MAX_LENGTH] = { 5,2,3,1,4 };
	int i,j,tmp;
	for(i = 1; i < MAX_LENGTH; i++){
		showData(array,MAX_LENGTH);
		j = i;
		//	定められた範囲内で、順序の入れ替えが必要な場合の処理
		while(j >= 1 && array[j-1] < array[j]){
			//	値の入れ替え
			tmp = array[j];
			array[j]  = array[j-1];
			array[j - 1] = tmp;
			j--;
			showData(array,MAX_LENGTH);
		}
	}
	showData(array,MAX_LENGTH);
}

//	配列の表示
void showData(int* array,int length){
	int i;
	for(i = 0; i < length; i++){
		printf("%d ",array[i]);
	}
	printf("\n");
}
実行結果1
5 2 3 1 4
5 2 3 1 4
5 3 2 1 4
5 3 2 1 4
5 3 2 4 1
5 3 4 2 1
5 4 3 2 1

イメージとしては最初の要素と次の要素という2つの要素をまずは並べ替えて順序道理にし、さらにその中に次のようを加えて、その中での順序通りに並べていく、ということを繰り返していくイメージです。

先頭から並べ替えながら、次の要素をふさわしい場所に挿入していく、というイメージを持つとわかりやすいでしょう。