C言語によるシェルソートの実装

サンプルプログラム

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

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

#define MAX_LENGTH  8
 
void showData(int*,int);

void main(){
	int array[MAX_LENGTH] = { 41,23,55,36,14,32,59,90 };
	int i, j, step, tmp;
	//	飛ばしていく数を設定
	step = MAX_LENGTH / 2;
	while (step > 0)
	{
		//	途中結果の表示
		showData(array,MAX_LENGTH);
		for(i=0; i < MAX_LENGTH; i++)
		{
			j = i;
			tmp = array[i];
			//	順序が適切でなければ、並べ替えを行う
			while (j >= step && array[j - step] < tmp){
				array[j] = array[j - step];
				j -= step;
			}
			array[j] = tmp;
		}
		step /= 2;
	}
	//  最後にもう一度結果表示
    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
41 23 55 36 14 32 59 90
41 32 59 90 14 23 55 36
59 90 55 36 41 32 14 23
90 59 55 41 36 32 23 14

シェルソートの特徴は、データを細かく分けて、その中でシェルソートを行う点にあります。領域は次第に統合されていきますが、すでに細かい段階である程度並べ替えが行われているので、範囲がある程度長くなっても並べ替えの手間数は単純な挿入ソートよりは少なくなっています。