14.3 節のプログラムがバブルソートとクイックソートをするプログラムである. このプログラムを解説しよう.
anArray[0] | anArray[1] | anArray[2] | ![]() |
anArray[Size-1] |
クイックソートではまず, M より小さいデータを, M の左に, M より大きいデータを, M の右にあつめる. これを実行しているのが, 関数 quickSort の while ループである. そのあと, M に左および右にまたクイックソートを 再帰的に適用することによりソートを完成させる.
[346] load("sort.rr"); 1 [347] load("sort2.rr"); 1 [348] testBuble(7); 0.000644sec(0.00064sec) 0 [349] testQuick(7); 0.000723sec(0.00073sec) 0というぐあいにバブルのほうが早い. このことから, 漸近的な計算量のうえでは, クイックソートの方が早いが, データが少ない時は単純なアルゴリズムのほうがプログラムが 単純になってはやいことがわかる. では, つぎにデータの数を 70 としてやってみよう.
[357] testBuble(70); 0.0406sec + gc : 0.04641sec(0.09074sec) 0 [358] testQuick(70); 0.008668sec(0.008675sec) 0ということで, クイックソートの方が早くなる.
データ数が 700 になると, クイックソートの方が
断然はやい.
(,
だが,
,
である.)
[364] testBuble(700); 4.088sec + gc : 1.476sec(5.571sec) 0 [365] testQuick(700); 0.1606sec + gc : 0.04788sec(0.2147sec) 0