バブルソートと クイックソート

14.3 節のプログラムがバブルソートとクイックソートをするプログラムである. このプログラムを解説しよう.

1. データのサイズはそれぞれ testBuble および testQuick の N で指定する.
2. データは配列(ベクトル) A に乱数をいれて初期化する.
3. quickSort(A,P,Q) は A の $P$ 番めから $Q$ 番めまでを クイックソートする.
4. tstart() で時間計測開始, tstop() で時間計測終了および 時間表示である.
5. バブルソートの計算量は $O(n^2)$, クイックソートの平均計算量は, $O(n \log n)$ である.

バブルソートでは, 配列 anArray の隣同士の元を 比較して, 大きいものから順にどんどん下図の右に集める.

anArray[0]

anArray[1]

anArray[2]

$\cdots$

anArray[Size-1]

関数 bubleSort の変数 J と I による 2 重ループでこれを実現している.

クイックソートではまず, M より小さいデータを, M の左に, M より大きいデータを, M の右にあつめる. これを実行しているのが, 関数 quickSort の while ループである. そのあと, M に左および右にまたクイックソートを 再帰的に適用することによりソートを完成させる.

例題 13.1   [10]      大きさ 7 のデータと大きさ 70, および 700 のデータをバブルソート, クイックソートして その実行時間を調べなさい. アルゴリズムの違いで計算の速度がかわることを実感してもらいたい.

入力例 13.1        まずはデータの数を 7 として, やってみよう.

[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 になると, クイックソートの方が 断然はやい. ($70^2= 4900$, $70 \log 70 \simeq 297$ だが, $700^2 = 490000$, $700 \log 700 \simeq 4586$ である.)

[364] testBuble(700);
4.088sec + gc : 1.476sec(5.571sec)
0
[365] testQuick(700);
0.1606sec + gc : 0.04788sec(0.2147sec)
0

問題 13.1   [10]      N の値をいろいろ変えて計算時間を測定し, グラフ用紙にグラフとして書いてみよう.