プログラミング修行その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の方は目視で確認するのやだし・・
まぁいいか。