- 挿入中
- 比較中
- 交換済み
- 整列済みの部分
挿入ソート
挿入ソートは、多くの人が手札のトランプを並べるのと同じやり方です。リストの先頭に整列済みの部分を保ち、次の値を取り出して、それより大きい値をすべて越えて収まる位置まで戻します。好きな速度で再生したり、比較を1回ずつ進めたりしながら、比較、交換、パスのカウンターを見てみましょう。 「再生」で並べ替えを見るか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。タイルには比較回数、交換回数、パス数が表示されます。棒の数や初期の並びを選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 棒の数と初期の並びを選びます:ランダム、ほぼ整列済み、逆順、重複が多い。数値を自分で入力することもできます。
- 「再生」を押すか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると、並べ替えの好きな位置に移動できます。
- ほぼ整列済みのリストと逆順のリストを試して、比較回数を比べてみましょう。
挿入ソートの仕組み
最初の値だけで、整列済みの部分になります。2番目の値を取り出し、その前の値と比較します。前の値の方が大きければ交換し、前の値が大きくなくなるか、値が先頭に着くまで比較と交換を続けます。これで最初の2つの値が順に並びます。3番目、4番目と、リストの最後まで同じことを繰り返します。
ほぼ整列済みのリストで速い
各パスは大きくない値に出会った時点で止まるので、もともと正しい位置に近い値は1〜2回の比較で済みます。整列済みのリストは比較n − 1回、交換0回です。最悪の場合である逆順のリストでは、比較も交換もn(n − 1)/2回です。交換回数は常に初期リストの転倒数、つまり順序が逆のペアの数と等しくなります。そのため挿入ソートは、短いリストやほぼ整列済みのリストによく使われ、より速いソートの中で小さな部分を仕上げるのにも使われます。
よくある質問
挿入ソートはどのように動きますか?
リストの先頭に整列済みの部分を作っていきます。各パスで次の値を取り出し、前にあるより大きい値をすべて越えて、収まる位置まで戻します。k回目のパスの後、最初のk + 1個の値は順に並びますが、後の値がその間に挿入されることはあります。
挿入ソートの比較回数と交換回数は?
交換回数は常に初期リストの転倒数と等しく、整列済みのリストなら0回、逆順のリストならn(n − 1)/2回です。比較回数は交換回数に1パスあたり最大1回を足したものなので、n − 1回からn(n − 1)/2回の間です。
なぜ挿入ソートはほぼ整列済みのリストで速いのですか?
パスは大きくない値に出会うとすぐに止まるからです。どの値も最終位置に近ければ各パスは短く、ソート全体にかかる時間はnに近くなります。
挿入ソートは安定ですか?
はい。値は自分より真に大きい値しか越えないので、等しい値同士が入れ替わることはなく、元の順序が保たれます。
入力した数値はどこかに送信されますか?
いいえ。並べ替えはブラウザ内で実行され、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ