- 比較中
- マーク(最小値・ピボット・キー)
- 交換・移動済み
- 確定
| 順位 | ソート | 比較・読み取り | 交換・移動 | 操作 |
|---|
ソート対決
最速のソートアルゴリズムはどれでしょう?それはリスト次第です。ソート対決は8種類のソートアルゴリズムを同じリストで同時に動かし、1つずつレーンに並べて、比較、読み取り、交換、移動を1回の操作として数えます。各レーンは回数が増えるにつれて進むので、効率のよいソートがゴールする間に遅いソートがまだ交換を続ける様子や、リストがほぼ整列済みや逆順のときに順位が入れ替わる様子を見られます。 「再生」で8種類のソートアルゴリズムが同じリストで競う様子を見るか、「ステップ」と「戻る」で操作を1回ずつ進めます。スライダーをドラッグすると好きな位置に移動できます。比較、読み取り、交換、移動はそれぞれ1回の操作として数え、各レーンは自分の操作回数に合わせて進むので、操作が最も少ないソートが最初にゴールします。棒の数や初期の並びを選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 棒の数と初期の並びを選びます:ランダム、ほぼ整列済み、逆順、重複が多い。数値を自分で入力することもできます。
- 「再生」を押して8つのレーンを見ます。「ステップ」と「戻る」で操作を1回ずつ進め、スライダーで対決の好きな位置に移動できます。
- 結果の表を比べたら、ほぼ整列済みのリストと逆順のリストも試して、順位の変化を見てみましょう。
対決のしくみ
8つのソートには同じリストが渡されます。2つの値の比較、基数ソートと計数ソートが読み取る桁や値、そして交換や移動を、それぞれ1回の操作として数えます。対決の各時点で、各レーンはその回数の操作でソートがどこまで進んだかを表示します。必要な操作が少ないソートほど早くゴールします。結果の表には、各ソートの比較回数、交換・移動回数、合計が並びます。
結果からわかること
ランダムな40個の値では、計数ソートは約120回、基数ソートは約240回、クイックソートは約260回、マージソートは約380回の操作が必要です。ヒープソートが約490回で続き、選択ソートと挿入ソートは約820回、バブルソートは1,100回を超えます。ほぼ整列済みのリストでは挿入ソートが約50回で勝ち、バブルソートが2位です。逆順のリストでは、バブルソートと挿入ソートはどちらも1,560回かかります。計数ソートと基数ソートがよく勝つのは、値が小さな整数だからです。それ以外のデータにはまったく使えません。
よくある質問
どのソートアルゴリズムが最速ですか?
データによります。小さな整数なら、計数ソートと基数ソートが最も少ない操作で済みます。一般的なデータなら、ランダムなリストではクイックソートとマージソートが最速で、ほぼ整列済みのリストでは挿入ソートが最速です。バブルソートと選択ソートは、ごく小さなリスト以外では遅くなります。
何が1回の操作になりますか?
2つの値の比較、基数ソートと計数ソートによる桁や値の読み取り、値の交換や移動が、それぞれ1回です。これは簡単なモデルで、実際の実行時間はメモリアクセスや各操作のコストにも左右されます。
なぜ計数ソートと基数ソートはよく勝つのですか?
値を比較しないからです。値が小さな整数であることを利用するので、作業量は n log n ではなく、n と値の範囲の和に比例して増えます。小さな整数でないデータには使えません。
なぜほぼ整列済みのリストでは挿入ソートが勝つのですか?
挿入ソートの作業量は、値の個数と順序が逆のペアの数の和だからです。ほぼ整列済みのリストにはそのようなペアがほとんどないので、各値は1つか2つ動くだけです。
入力した数値はどこかに送信されますか?
いいえ。対決はブラウザ内で動き、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ