ここでは、今までに説明したソートアルゴリズムを比較してみましょう。

下のアプレットは、6種類すべてのソートアルゴリズムを同時に実行するものです。

左上から右へ、バブルソート、バケットソート、基数ソート、ヒープソート、マージソート、クイックソートです。

"Start" ボタンを押すと、すべてのソートが同時開始されます。クイックソートがもっとも速く並べ終わり、次にバケットソート、基数ソートの順で並べ終わるのがわかります。

データ数や初期並びを変えて、いろいろなデータで試してみましょう。

アプレットの並べ替えプログラムは、人間の眼で見て並べ替えの様子がわかりやすいように、データの交換が起こるたびに wait を入れて速度を遅くして表示しています。しかし、この方法では、データの交換以外に要する時間はほとんど無視されることになり、正確な意味で正しい比較をしていることにはなりません。

そこで、wait を入れずに並べ替えを行うプログラムを作成し、いろいろな個数のデータを並べ替えてみて、その時間を測定しました。データは 1〜N の整数値で、初期状態ではランダムに並んでいます。

N を 100 から 100000 まで変化させて、100 回ずつ並べ替えを行った合計時間を、下のグラフに示します。参考までに、N log(N) と N*N のグラフも載せてあります。

これを見ると、並べ替えに要する時間の増え方は、バブルソートでは N*N に平行になっており、そのほかのソートではほぼ N*log(N) に平行になっていることがわかります。これは、前章までで説明したように、バブルソートの並べ替えのオーダーは O(N²)、その他のソートのオーダーは O(N log(N)) であることを示しています。

次に、並べ替えの速度ですが、もっとも速いのはやはりクイックソートになっており、2番目がヒープソート、以下、バケットソート、マージソート、基数ソートの順で、最後がバブルソートです。

しかし、データが100個〜400個の範囲では、基数ソート、マージソートよりもバブルソートのほうが速いと言う結果が出ました。この理由は、基数ソートでは基数を10、桁数を3に固定して行っていますので、常にバケツに3回入れることになることが考えられます。実際、データ数が少ないときは3桁ものバケツを準備する必要はなく、いわば無駄な処理を行っていることになります。また、マージソートでは、配列を併合するために、new 演算子により新しい配列を生成していますので、このオーバーヘッドに要する時間が、アルゴリズム本来のデータの比較や入れ替えの時間遅れを上回った結果、本来遅いはずのバブルソートのほうが速いと言う結果が出たと言うわけです。

この結果は、基数ソートの桁数をデータに合うように調整する、あるいはマージソートでは配列をあらかじめ準備して、実行中に new を使わないようにする等の対策を講じることで、回避できると考えられます。

次のグラフは、ヒープソートの並べ替え時間を 1 としたときの、各ソートの時間の比を表したものです。

平均すると、各ソートの速度比は次のようになります。

バケットソートは、データ数の少ない場合にはクイックソートを上回る場合もありますが、データ数が増えてくると約2倍の時間がかかります。上のグラフを見ると、データ数が 500 〜 5000 にかけて、ヒープソトーの速度が上下しているように見えますが、実際はクイックソートに要する時間が大きく変動しています（最初のグラフを見ると分かる）。ヒープソートの特徴は、データのばらつき方の影響をあまり受けないで、安定した速度でソートできると言うことにあります。

バケットソートの並べ替え時間がかなり一定しないのは、原因不明です。理論的には、バケットソートもデータの初期状態に依然せず、安定した速度で並べ替えを行うはずです。誰か原因がわかったら、教えてください。

なお、実験に使用した環境は以下の通りです。

← prev | next →