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

Introsort:分割の深さを監視して最悪時間を守る

クイックソートを基本に、偏った分割を検知してヒープソートへ切り替えるハイブリッド法を理解する。

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

更新日

この記事の目次
  1. 速い平均挙動と最悪上界を組み合わせる
  2. 偏った分割が続く場面
  3. 深さの制限が保証するもの
  4. 安定性と標準ライブラリの違い
  5. この記事をロゲイアに質問する理解を確かめる

速い平均挙動と最悪上界を組み合わせる

Introsortはクイックソートを基本とし、再帰の深さが予算を使い切った区間をヒープソートへ切り替える整列法です。典型的な深さ予算は元の要素数nに対する2⌊log₂n⌋程度ですが、具体的な係数や小区間の扱いは実装ごとに異なります。時間を時計で測って遅いと判断するのではなく、分割の構造から危険な進み方を見つけます。小さい区間には挿入ソートを使うこともありますが、それぞれの切り替え条件は別の役割を持っています。

偏った分割が続く場面

16要素で予算を8とする説明用の例を考えます。一回の分割で一要素しか確定しない進み方が続くと、区間は15、14、13要素とゆっくり縮みます。クイックソートを続ければ走査の総和が二次時間に膨らみますが、予算が尽きた時点の残る区間をヒープソートで終えれば、その先の偏った分割を止められます。実際の閾値を入力ごとにこの例へ固定する必要はありません。切り替えは全配列のやり直しではなく、まだ整列が終わっていない部分問題に適用します。

深さの制限が保証するもの

予算内の一つの分割レベルで走査される区間は互いに重ならず、その長さの合計は高々nです。レベル数をO(log n)に抑えれば、ここまでの分割費用はO(n log n)になります。残った区間のヒープソートも、それぞれの区間サイズに対するO(m log m)を合計してO(n log n)以内です。この説明には各分割が線形で比較が定数時間という前提があります。深さの監視だけで、不正な比較関数やオーバーフローした添字まで正しくなるわけではありません。

安定性と標準ライブラリの違い

通常のIntrosortは、クイックソートやヒープソートの交換を使うため安定ではありません。再帰スタックを抑えるには、小さい側だけを再帰し大きい側を反復処理する工夫も有効です。標準ライブラリが最悪O(n log n)比較を要求していることと、特定の版が必ず同じIntrosort実装を使うことは区別します。重複キーや既整列入力に対する分割法、挿入ソートの閾値なども実装の選択です。性能を述べるときは、コンパイラやライブラリの版と比較対象を明記します。

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

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

CS基礎を固める · STEP 10

学習コースから次を選ぶ