ソートアルゴリズムの比較

どんな場合でも最速というソートアルゴリズムはありません。単純だけれど遅いもの、ランダムなデータには速いのに整列済みのデータでつまずくもの、そもそも比較ソートではないものもあります。8つすべてを同じリストで競わせれば、違いがひと目でわかります。

ソートアルゴリズムごとに1本ずつ並んだ8本の棒のレーン。いくつかは整列済みで緑色になり、ほかはまだ整列されていない
ソートアルゴリズムごとに1本ずつ並んだ8本の棒のレーン。いくつかは整列済みで緑色になり、ほかはまだ整列されていない

3つのグループ

バブルソート、選択ソート、挿入ソートは単純なソートです。近くにある値を比較して交換し、ランダムなリストでは n² に比例する時間がかかります。マージソート、クイックソート、ヒープソートは作業を巧みに分割し、n log n に比例する時間で済みます。これは、2つの値のどちらが大きいかしか尋ねられないソートとしては最善です。基数ソートと計数ソートはこの問い自体を使いません。桁や値そのものを使うので、小さな整数のようなキーにしか使えません。

作業量の測り方

ソート対決では、比較、桁や値の読み取り、交換や移動をそれぞれ1回の操作として数えます。ランダムな40個の値では、計数ソートが約120回、基数ソートが240回、クイックソートが260回、マージソートが380回、ヒープソートが490回、選択ソートと挿入ソートがそれぞれ約820回、バブルソートが1,100回超です。実際のコンピューターではメモリも重要です。リストの中での動き方の違いから、クイックソートは実際には回数から想像するより速いことが多く、ヒープソートは遅くなります。

入力しだいで変わる

ほぼ整列済みのリストでは、40個の値に対して挿入ソートは約50回、バブルソートは約90回の操作で済みます。各値が正しい位置の近くにあるからです。逆順のリストでは、同じ2つが最悪の場合の1,560回かかります。選択ソート、ヒープソート、マージソート、基数ソート、計数ソートは並び順にほとんど左右されません。3つの値の中央値をピボットにするクイックソートは整列済みや逆順のリストもうまく処理しますが、単純なピボットでは整列済みのリストが最悪の場合になります。異なる値が少ないとクイックソートは遅くなります。等しい値がすべて片側に集まるからです。

メモリと安定性

バブルソート、選択ソート、挿入ソート、クイックソート、ヒープソートはインプレースで動き、追加のメモリはほとんど要りません。マージソート、基数ソート、計数ソートにはリストと同じ長さのバッファーが必要です。安定なソートは等しい値を元の順序のまま保ちます。バブルソート、挿入ソート、マージソート、基数ソート、計数ソートは安定で、選択ソート、クイックソート、ヒープソートは安定ではありません。レコードを複数の項目で順に並べ替えるときに、安定性が重要になります。

どれを使うべきか

実際には、プログラミング言語に組み込まれたソートを使います。たいていは Timsort(短い部分には挿入ソートを使い、一部が整列済みのデータに速いマージソート)か、introsort(ヒープソートに切り替えることがあり、小さな部分には挿入ソートを使うクイックソート)です。小さな整数のキーが大量にあるなら、計数ソートや基数ソートが両方に勝つこともあります。バブルソートと選択ソートは主に教材です。

試してみよう

ソート対決を開いて「再生」を押してください。各レーンは同じリストに対する1つのソートで、右の数字が操作回数を数え、終わるとレーンが緑色になります。ほぼ整列済み、逆順、重複が多いリストを試して、ゴールの順番が変わる様子を見てみましょう。各ソートには専用のアプリもあり、1ステップずつ詳しくたどれます。

よくある質問

最速のソートアルゴリズムは何ですか?

一般的なデータでは、クイックソートとマージソート(それらをもとにした introsort や Timsort などのハイブリッド)が平均して最速で、n log n です。小さな整数のキーなら、計数ソートと基数ソートがさらに速くなります。短いリストやほぼ整列済みのリストでは挿入ソートが勝ちます。

なぜ比較ソートは n log n を超えられないのですか?

n 個の値のリストには n! 通りの並びがあり、1回の比較の結果は2通りなので、最悪の場合すべてを区別するには少なくとも log₂(n!) 回の比較が必要です。これはおよそ n log₂ n です。基数ソートと計数ソートは比較しないので、この限界を受けません。

安定なソートアルゴリズムはどれですか?

バブルソート、挿入ソート、マージソート、基数ソート、計数ソートは、通常の形では安定です。選択ソート、クイックソート、ヒープソートは値を遠くまで動かすので安定ではありません。

追加のメモリが必要なソートはどれですか?

マージソート、基数ソート、計数ソートには、リストとほぼ同じ長さのバッファーが必要です。バブルソート、選択ソート、挿入ソート、ヒープソートはほとんど不要で、クイックソートは再帰のために少し使うだけです。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

ソート対決を始める