比較
交換
パス

  • 挿入中
  • 比較中
  • 交換済み
  • 整列済みの部分

挿入ソートの詳細

挿入ソート

挿入ソートは、多くの人が手札のトランプを並べるのと同じやり方です。リストの先頭に整列済みの部分を保ち、次の値を取り出して、それより大きい値をすべて越えて収まる位置まで戻します。好きな速度で再生したり、比較を1回ずつ進めたりしながら、比較、交換、パスのカウンターを見てみましょう。 「再生」で並べ替えを見るか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。タイルには比較回数、交換回数、パス数が表示されます。棒の数や初期の並びを選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. 棒の数と初期の並びを選びます:ランダム、ほぼ整列済み、逆順、重複が多い。数値を自分で入力することもできます。
  2. 「再生」を押すか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると、並べ替えの好きな位置に移動できます。
  3. ほぼ整列済みのリストと逆順のリストを試して、比較回数を比べてみましょう。

挿入ソートの仕組み

最初の値だけで、整列済みの部分になります。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 を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ