ソートアルゴリズムの比較
どんな場合でも最速というソートアルゴリズムはありません。単純だけれど遅いもの、ランダムなデータには速いのに整列済みのデータでつまずくもの、そもそも比較ソートではないものもあります。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 を開きます。インストール不要、始めるのにクレジットカードも不要です。
ソート対決を始める