アルゴリズム・データ構造図鑑 · 基礎から応用へ

挿入ソート:整列した接頭辞へ一つずつ差し込む

挿入位置まで要素をずらす動作を追い、反転数と実行時間、安定性の関係を理解する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 整列済み部分を一つ増やす
  2. 5、2、4、2を追う
  3. 反転数が移動回数を決める
  4. 二分探索を足しても移動は残る
  5. この記事をロゲイアに質問する理解を確かめる

整列済み部分を一つ増やす

挿入ソートは、配列の左側を整列済みの領域として維持し、その直後の要素を適切な位置へ入れます。挿入する値を一時的に退避し、それより大きい要素を右へずらし、空いた場所へ値を置きます。外側の反復が位置iへ来た時点で、区間[0,i)は整列している、という不変条件が説明の軸です。右側は未整列のままで構わず、全体から最小値を毎回探す必要もありません。比較する値と移動するレコードを混同しないことが大切です。

5、2、4、2を追う

[5,2,4,2]では、最初の2を退避して5を一つ右へずらすと[2,5,4,2]になります。次の4は5だけを越えて[2,4,5,2]へ入り、最後の2は5と4を越えて[2,2,4,5]へ入ります。同じ値の2を元の位置で区別しておくと、厳密に大きい要素だけをずらす場合は最初の2が先に残ることが分かります。等しい要素まで越えてしまう条件では、この安定性は保たれません。値だけでなく出現順も書いて追跡しましょう。

反転数が移動回数を決める

反転とは、先にある値の方が後の値より大きい組です。隣接する要素をずらす実装では、挿入による移動は反転を解消する操作に対応します。反転数をIとすると、定数時間比較の下で処理量はO(n+I)と説明でき、既に整列済みなら線形時間です。逆順の異なるn要素にはn(n−1)/2組の反転があるため二次時間になります。どちらも最悪O(n²)という一言で済ませると、ほぼ整列した小区間で使いやすい理由が見えなくなります。

二分探索を足しても移動は残る

挿入位置を二分探索すれば比較回数は減らせますが、連続配列の途中へ要素を入れる移動は消えません。そのため二分挿入ソートを一般のO(n log n)時間の整列とみなすのは誤りです。通常の実装の追加領域はO(1)ですが、大きなレコードのコピーや高価な比較では費用の内訳が変わります。空配列、要素一つ、同じキーが並ぶ入力を試し、比較関数が整合した順序を与えることも確認します。巨大で乱れた入力には別の整列法が適しています。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ