プログラミング修行その3:シェルソート

Cでシェルソートを実装しtみた
前回のインサーションソートの改良版であるシェルソートを実装する。
シェルソートはhだけ離れた要素同士を比較交換することで効率よくソートする方法。
実際に交換するときはインサートソート。
hはなるべく大き目の値からはじめて、段々小さくしていく。
以下コード

// シェルソート関数
int my_shell_sort(double *numbers, int size)
{
	int h;
	int i,j;
	double keep;
	for( h = size/2; h > 0; h /= 2){
		for( i = h; i < size; i++){
			for( j = i-h; j>= 0 && numbers[j] > numbers[j+h]; j -= h){
				keep = numbers[j];
				numbers[j] = numbers[j+h];
				numbers[j+h] = keep;
			}
		}
	}
	return 0;
}
// シェルソート関数(途中経過表示)
int my_shell_sort2(double *numbers, int size)
{
	int h;
	int i,j;
	double keep;
	for( h = size/2; h > 0; h /= 2){
		for( i = h; i < size; i++){
			for( j = i-h; j>= 0 && numbers[j] > numbers[j+h]; j -= h){
				keep = numbers[j];
				numbers[j] = numbers[j+h];
				numbers[j+h] = keep;
				printf("h=%d, i=%d, j=%d\n",h,i,j);
				print_numbers(numbers,size);
				printf("\n");
			}
		}
	}
	return 0;
}

実行結果
「mySorting.txt」の実行結果

C:\C_syugyo>mySorting -s mysorting.txt
size = 100
 14.877640 79.914590 32.045770 52.476480 37.376090
 92.927020 95.669520 12.440200 79.360010 58.551780
 45.727100 50.345710 64.642580 44.169590 80.479340
 77.848120 36.762130 59.630120 14.712820 51.976750
 23.641630 8.721956 29.200960 4.217992 45.305730
 77.460750 62.698490 7.304937 41.109140 88.782880
 78.649440 28.693430 20.215190 86.042780 86.713230
 73.772200 32.838140 32.056420 50.906930 93.622220
 33.200980 19.047090 24.127970 57.448270 8.226496
 3.016102 18.803320 63.085480 32.344780 48.016980
 75.358230 59.009640 88.930370 88.979370 40.268420
 10.328820 54.731230 45.872620 68.847730 70.792270
 0.233562 70.414570 13.862590 62.187930 73.530010
 67.427530 50.306000 65.187940 5.185891 41.066010
 90.836780 53.066320 50.268220 81.684910 92.291410
 85.356830 80.629880 20.716590 44.080740 14.665740
 7.861154 23.080270 88.060540 73.816520 96.861380
 58.215970 3.407331 56.663430 67.481170 50.700820
 56.702930 36.166030 15.315430 31.357360 68.830370
 10.465220 23.642010 56.160760 75.300150 60.662540
シェルソート(shell sort)
ソート完了
 0.233562 3.016102 3.407331 4.217992 5.185891
 7.304937 7.861154 8.226496 8.721956 10.328820
 10.465220 12.440200 13.862590 14.665740 14.712820
 14.877640 15.315430 18.803320 19.047090 20.215190
 20.716590 23.080270 23.641630 23.642010 24.127970
 28.693430 29.200960 31.357360 32.045770 32.056420
 32.344780 32.838140 33.200980 36.166030 36.762130
 37.376090 40.268420 41.066010 41.109140 44.080740
 44.169590 45.305730 45.727100 45.872620 48.016980
 50.268220 50.306000 50.345710 50.700820 50.906930
 51.976750 52.476480 53.066320 54.731230 56.160760
 56.663430 56.702930 57.448270 58.215970 58.551780
 59.009640 59.630120 60.662540 62.187930 62.698490
 63.085480 64.642580 65.187940 67.427530 67.481170
 68.830370 68.847730 70.414570 70.792270 73.530010
 73.772200 73.816520 75.300150 75.358230 77.460750
 77.848120 78.649440 79.360010 79.914590 80.479340
 80.629880 81.684910 85.356830 86.042780 86.713230
 88.060540 88.782880 88.930370 88.979370 90.836780
 92.291410 92.927020 93.622220 95.669520 96.861380

「mySorting2.txt」の実行結果

C:\C_syugyo>mySorting -S mysorting2.txt
size = 10
 59.000000 13.000000 38.000000 91.000000 48.000000
 27.000000 66.000000 45.000000 13.000000 38.000000
シェルソート(shell sort)
h=5, i=5, j=0
 27.000000 13.000000 38.000000 91.000000 48.000000
 59.000000 66.000000 45.000000 13.000000 38.000000

h=5, i=8, j=3
 27.000000 13.000000 38.000000 13.000000 48.000000
 59.000000 66.000000 45.000000 91.000000 38.000000

h=5, i=9, j=4
 27.000000 13.000000 38.000000 13.000000 38.000000
 59.000000 66.000000 45.000000 91.000000 48.000000

h=2, i=7, j=5
 27.000000 13.000000 38.000000 13.000000 38.000000
 45.000000 66.000000 59.000000 91.000000 48.000000

h=2, i=9, j=7
 27.000000 13.000000 38.000000 13.000000 38.000000
 45.000000 66.000000 48.000000 91.000000 59.000000

h=1, i=1, j=0
 13.000000 27.000000 38.000000 13.000000 38.000000
 45.000000 66.000000 48.000000 91.000000 59.000000

h=1, i=3, j=2
 13.000000 27.000000 13.000000 38.000000 38.000000
 45.000000 66.000000 48.000000 91.000000 59.000000

h=1, i=3, j=1
 13.000000 13.000000 27.000000 38.000000 38.000000
 45.000000 66.000000 48.000000 91.000000 59.000000

h=1, i=7, j=6
 13.000000 13.000000 27.000000 38.000000 38.000000
 45.000000 48.000000 66.000000 91.000000 59.000000

h=1, i=9, j=8
 13.000000 13.000000 27.000000 38.000000 38.000000
 45.000000 48.000000 66.000000 59.000000 91.000000

h=1, i=9, j=7
 13.000000 13.000000 27.000000 38.000000 38.000000
 45.000000 48.000000 59.000000 66.000000 91.000000

ソート完了
 13.000000 13.000000 27.000000 38.000000 38.000000
 45.000000 48.000000 59.000000 66.000000 91.000000



感想
さすがにここらへんからはちょっとコードがややこしくなってきてる。
擬似コードとかがそこらへんに転がっているから実装できるw
俺のプログラミング能力やばすぎ orz
でも、ややこしくなってきてる分だけ値の交換回数は減ってきてる気がする。
('A`)あ〜交換回数数えるコード混ぜときゃよかった(mySorting.txtの方は目視で確認するのやだし・・
まぁいいか。