プログラミング修行その2:インサーションソート
プログラミングの練習としてインサーションソートをCで実装してみる
インサーションソートはソート済みの配列にデータを適切な場所に1つずつ挿入していく方法。
実装上はバブルソートとは反対に配列の左端にソート済みのデータが並んでいくことになる。
速度はバブルソートよりは速いって程度。
でCのコード。main関数は前回のをちょっと修正しただけだから省略。
// インサーションソート関数 int my_insertion_sort(double *numbers, int size) { double data,keep; int i,j; for(i = 1; i < size; i++){ data = numbers[i]; j = i; while( numbers[j-1] > data){ keep = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = keep; j--; } numbers[j] = data; } return 0; } // インサーションソート関数(途中経過表示) int my_insertion_sort2(double *numbers, int size) { double data,keep; int i,j; for(i = 1; i < size; i++){ data = numbers[i]; j = i; while( numbers[j-1] > data){ keep = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = keep; j--; } numbers[j] = data; print_numbers(numbers,size); printf("\n"); } return 0; }
実行結果
「mySorting.txt」での実行結果
C:\C_syugyo>mySorting -i 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 インサーションソート(insertion 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 -I mysorting2.txt size = 10 59.000000 13.000000 38.000000 91.000000 48.000000 27.000000 66.000000 45.000000 13.000000 38.000000 インサーションソート(insertion sort) 59.000000 13.000000 38.000000 91.000000 48.000000 27.000000 66.000000 45.000000 13.000000 38.000000 13.000000 59.000000 38.000000 91.000000 48.000000 27.000000 66.000000 45.000000 13.000000 38.000000 13.000000 38.000000 59.000000 91.000000 48.000000 27.000000 66.000000 45.000000 13.000000 38.000000 13.000000 38.000000 59.000000 91.000000 48.000000 27.000000 66.000000 45.000000 13.000000 38.000000 13.000000 38.000000 48.000000 59.000000 91.000000 27.000000 66.000000 45.000000 13.000000 38.000000 13.000000 27.000000 38.000000 48.000000 59.000000 91.000000 66.000000 45.000000 13.000000 38.000000 13.000000 27.000000 38.000000 48.000000 59.000000 66.000000 91.000000 45.000000 13.000000 38.000000 13.000000 27.000000 38.000000 45.000000 48.000000 59.000000 66.000000 91.000000 13.000000 38.000000 13.000000 13.000000 27.000000 38.000000 45.000000 48.000000 59.000000 66.000000 91.000000 38.000000 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