この実験について
バブルソート、挿入ソート、マージソートが同じ入力を昇順に並べ替える様子を確認しましょう。比較の時点で一時停止したり、書き込みを1つずつ進めたり、トレース全体を逆方向にたどったりできます。値の比較回数とメイン配列への書き込み回数を別々に数えることで、アルゴリズムの処理量とアニメーションの長さを区別できます。
学習目標
- 3つの比較ソートアルゴリズムにおける比較と書き込みのトレース
- シャッフル済み、ソート済み、逆順の入力で性能を比較する
- 二次的な最悪時の増加と n log n の増加を見分ける
使い方
- 1シャッフル済みの入力と配列の長さを固定します。バブルソートを最後まで実行し、比較回数と書き込み回数を記録します。
- 2同じ入力を使って、挿入ソート、次にマージソートを最初から実行します。最終的な回数を比較します。
- 3ソート済みの入力を試し、バブルソートの早期終了と、挿入ソートの比較回数が少ないことを確認しましょう。
- 4Previous とトレーススライダーを使って、マージの過程を確認できます。一時バッファには、元のメイン配列の位置では見えなくなった値が保持されることがあります。
モデル
前提条件
- 入力には1からnまでの重複しない整数が含まれます。シャッフルには固定シードを使うため、すべてのアルゴリズムに同じデータが渡されます。
- 比較とは、インデックスやループの上限ではなく、データ値同士を判定することです。書き込みとは、変更されない挿入キーも含め、メイン配列への代入を指します。
- マージソートで一時バッファにコピーする処理は、書き込み回数に含まれません。追加のメモリ使用量も、表示される操作合計には含まれません。
- 再生速度は学習用に設定されており、実時間での性能を測定するものではありません。
授業で試してみましょう
- Q1この実装では、入力がすでに整列済みの場合、なぜバブルソートの比較回数は n − 1 回だけなのでしょうか？
- Q2配列の長さが同じ場合、逆順の入力に対して比較回数が少ないのはどのアルゴリズムですか？
- Q3アニメーションのフレーム数がアルゴリズムの速度を測る信頼できる指標ではないのはなぜですか？
よくある質問
挿入ソートやマージソート中に、値が一時的に重複して表示されるのはなぜですか？
値は、一時的なキーやマージ用バッファに保持されたまま、メイン配列が上書きされることがあります。この可視化では、書き込みのたびにメイン配列の内容を表示します。処理が完了すると、値の重複は解消されます。
マージソートは常に書き込み回数が少なくなりますか？
いいえ。マージソートは比較回数の増加を効率的に抑えますが、マージした結果を繰り返し書き戻します。操作回数は入力データや、どの代入を数えるかによって異なります。