このページでは、バブル・選択・挿入の基本整列法と、クイック・ヒープ・マージの高速整列法の手順、計算量、安定性の違いがわかります。
- 一言で言うと：
- データを小さい順（または大きい順）に並べ替える方法の話。遅いが単純な3つの基本整列法と、速い3つの整列法（クイック、ヒープ、マージ）、その考え方と計算量・安定性が出てくる。
基本の3つ（バブル・選択・挿入）→ 考え方で分ける（逐次添加・分割統治・データ構造）→ 速い3つ（クイック・ヒープ・マージ）
覚え方の軸
- 速さで2グループ：
- 基本整列法（バブル、単純選択、単純挿入）はO(n²)、高速整列法（クイック、ヒープ、マージ）はO(n log n)
- 基本3つは「何をするか」の動詞で区別：
- バブル＝隣と交換、選択＝最小を選んで先頭へ、挿入＝正しい位置に差し込む
- 安定かどうかの○×：
- 安定＝バブル、単純挿入、マージ。安定でない＝クイック、ヒープ（単純選択は実装しだい）
- 例外を押さえる：
- 単純挿入は最良O(n)（ほぼ整列済みに強い）、クイックは最悪O(n²)（整列済みで最小・最大を基準値にしたとき）
- 考え方は3つ：
- 1つずつ増やす（逐次添加法）、分けて解く（分割統治法：クイック・マージ）、データ構造を使う（ヒープ）
基本的な整列アルゴリズム：遅いけれど単純な3つ
- 整列（ソート）：
- 1列に並んだデータを、ある規則に従って並べ替える処理
- 安定な整列：
- 同じキー値をもつデータの順序が、整列の前と後で変わらないもの
- 基本整列法のうち、バブルソートと単純挿入法は安定
- 単純選択法は、実装するアルゴリズムしだいで安定にもできる
- 3つの基本整列法
| 整列法 | 別名 | やり方 |
|---|---|---|
| バブルソート | 隣接交換法 | 隣り合う要素を比べ、大小が逆なら交換する。交換が要らなくなるまで繰り返す |
| 単純選択法 | 最小値（最大値）選択法 | 未整列の中から一番小さい（大きい）要素を選び、未整列部分の先頭と入れ替える。最後から2番目に正しい要素が入るまで繰り返す |
| 単純挿入法 | − | 未整列の先頭の要素を取り出し、整列済みの中の正しい位置に挿入していく |
- バブルソートの例（7 4 9 5 を昇順に）：
- 1回目：
- 7と4を交換 → 4 7 9 5、7と9はそのまま、9と5を交換 → 4 7 5 9（最大値9が末尾に決まる）
- 2回目：
- 7と5を交換 → 4 5 7 9
- 3回目：
- 比べても交換なし 4 5 7 9
- 1回目：
- 単純選択法の例（7 4 9 5 を昇順に）：
- 最小値4を見つけて先頭と交換 → 4 7 9 5
- 残りから最小値5を見つけて2番目と交換 → 4 5 9 7
- 残りから最小値7を見つけて3番目と交換 → 4 5 7 9
- 単純挿入法の例（7 4 9 5 を昇順に）：
- 7を整列済みとみなす
- 7と4を比べ、4を正しい位置に挿入 → 4 7 9 5
- 7と9を比べ、順が正しいのでそのまま → 4 7 9 5
- 9と5を比べ、逆なので5を1つずつ前と比べて正しい位置に挿入 → 4 5 7 9
- シェルソート（改良挿入法）：
- 一定の間隔おきに取り出した要素の部分列を、それぞれ単純挿入法で整列し、間隔を狭めて同じ操作を繰り返す。間隔が1になるまで続ける
- 計算量（整列の計算量は比較回数で評価する）
- バブルソートと単純選択法の比較回数は、データ数nのとき n(n−1)／2回 → O(n²)
- 単純挿入法の比較回数は、最悪 n(n−1)／2回、最良 n−1回
- 単純挿入法の計算量は、平均と最悪がO(n²)、最良がO(n)
- 元のデータがほぼ正しい順に並んでいると、単純挿入法の計算量はO(n)に近くなる
- 例題：
- データ数10のバブルソートの比較回数は 10×9÷2＝45回
- 単純挿入法なら、すでに整列済みのとき（最良）は 10−1＝9回
- 計算量が n log₂n、つまり O(n log n) の高速な整列法として、クイックソート、ヒープソート、マージソートがある（後述）
整列法の考え方：3つの発想
- データ整列法の考え方は、大きく分けて逐次添加法、分割統治法、データ構造の利用の3つ
- このほかにランダム化法という考え方もある
- 逐次添加法：
- n個を整列する途中で、（k−1）個が整列済みのとき、1つの要素を加えて整列済みをk個にする。これをk＝2、3、4、…、nまで繰り返す
- バブルソート、単純選択法、単純挿入法がこの考え方
- 分割統治法：
- 大きな問題を小さな問題に分割し、それぞれの解を結合して全体の解を求める考え方
- 分割とは、対象の集合や定義域を分けること。分割処理の多くは再帰的な処理で行う
- クイックソートとマージソートがこの考え方
- データ構造の利用：
- 整列の効率を上げるためにデータ構造を使う考え方
- 一番代表的なのがヒープソート
- 単純挿入法でも、整列済みのデータを2分探索木で表せば、計算量をO(n log n)に抑えられる
- 二分挿入法：
- 挿入する場所を2分探索法で探す方法
高速な整列アルゴリズム：速い3つ
- クイックソート：
- 整列対象から中間的な基準値を選び、それより小さい値の区分と大きい値の区分に振り分けて分割する。分割した区分ごとに再帰的にクイックソートを行い、データ数が1つになるまで繰り返す
- 基準値は、軸またはピボット（pivot）ともいう
- 分割統治法の考え方。高速だが、安定ではない
- 平均計算量はO(n log n)
- ★最悪はO(n²)：
- あらかじめ整列されたデータに対して、最小値か最大値を基準値にした場合（分割が片寄って、毎回1個しか減らない）
- 試験では「どんなときに計算量が最悪になるか」が問われる
- 安全クイックソート：
- 最悪でもO(n log n)に抑える方法の一つ。再帰呼出しの回数（段数）が一定を超えたらヒープソートに切り替える
- 例（15 9 18 12 20 8 6、基準値12）：
- 12より小さい「9 8 6」と、大きい「15 18 20」に分ける
- それぞれ基準値8、18で同じことを繰り返す → 6 8 9 12 15 18 20
- ヒープソート：
- ヒープ：
- 各節に「親のデータ≦子のデータ」（またはその逆）の関係をもたせた順序木
- ヒープは完全2分木か、完全2分木の葉を右からいくつか取り除いた形になる
- 親と子の間にだけ順序が決まっていて、兄弟どうしには決まりがないので、厳密には半順序木
- 降順に整列する手順：
- 未整列のデータで「親≦子」のヒープを作り、配列で表す → ヒープの根（配列の先頭）にある最小値を取り出して整列済みの部分に移す → ヒープを再構成する。この「根の取り出し → ヒープの再構成」を繰り返して、未整列部分を縮めていく
- 昇順に整列するときは、「親≧子」のヒープを作る
- 配列での表し方：
- 根をT［1］に置き、T［i］の左の子をT［2×i］、右の子をT［2×i＋1］に置く
- 高速で、どんなデータ列でも計算量はO(n log n)で変わらない。ただし安定ではない
- ヒープの再構成の例（T＝3 6 10 9 14 16 11）：
- 根の3を取り出し、ヒープの最後のデータ11を根に移す（空いたところには取り出した3を整列済みとして入れる）→ 11 6 10 9 14 16 ｜3
- 11より小さい子（6と10）があるので、小さい方の子6と交換 → 6 11 10 9 14 16
- 11より小さい子（9と14のうち9）があるので、9と交換 → 6 9 10 11 14 16。これで「親≦子」が回復
- ヒープソートの処理概要
- ① nにヒープの大きさ（節数）を入れる
- ② nが1になるまで、③〜⑥を繰り返す
- ③ T［1］とT［n］を入れ替える
- ④ nを1減らす（ヒープを1つ小さくする）
- ⑤ rに1を入れる
- ⑥ T［r］より小さい値の子がある間、小さい方の子とT［r］を交換し、rに交換した子の添字を入れる（⑤⑥がヒープの再構成）
- 最初にヒープを作る処理：
- ① i＝節数÷2 ② i＜1になるまで、T［i］を根としてヒープを再構成し、iを1減らす
- 例：
- 節数7なら、i＝3、2、1の順に再構成する（葉ではない節を、下の方から順に整える）
- ヒープ：
- マージソート：
- 整列対象のデータ列の分割と併合（マージ）を繰り返し、最後に1つの整列済みデータ列を作る
- 大きさが1になれば、整列済み（整列完成）とみなす。分割する大きさmは場合によって違う（ここではm＝1）
- 例（6 3 8 1）：
- 前半「6 3」と後半「8 1」に分割（①）→ 前半を「6」「3」に分割（②）→ 併合して「3 6」（④）→ 後半を「8」「1」に分割（③）→ 併合して「1 8」（⑤）→ 全体を併合して「1 3 6 8」（⑥）
- 前半 → 後半の順に再帰的に処理するので、処理順は ①→②→④→③→⑤→⑥
- 分割統治法の考え方で、再帰処理を使う
- どんなデータ列でも計算量はO(n log n)で、安定
- データ数の半分程度の作業領域が必要
- 外部記憶装置上の大量のデータの整列に使われる
| 整列法 | 平均 | 最悪 | 安定 | 考え方・特徴 |
|---|---|---|---|---|
| バブルソート | O(n²) | O(n²) | ○ | 逐次添加法。隣と交換 |
| 単純選択法 | O(n²) | O(n²) | 実装しだい | 逐次添加法。最小を選ぶ |
| 単純挿入法 | O(n²) | O(n²) | ○ | 逐次添加法。最良O(n) |
| クイックソート | O(n log n) | O(n²) | × | 分割統治法。基準値で分ける |
| ヒープソート | O(n log n) | O(n log n) | × | データ構造の利用 |
| マージソート | O(n log n) | O(n log n) | ○ | 分割統治法。作業領域が要る |
混同しやすいペア
- バブルソート（隣と交換）／単純選択法（最小を選んで先頭と入れ替え）／単純挿入法（正しい位置に差し込む）
- 安定（バブル、単純挿入、マージ）／安定でない（クイック、ヒープ）
- クイックソート（平均O(n log n)、最悪O(n²)）／ヒープソート・マージソート（いつもO(n log n)）
- 単純挿入法の最良（O(n)、ほぼ整列済み）／クイックソートの最悪（O(n²)、整列済みで最小・最大を基準値にしたとき）
- 逐次添加法（バブル、選択、挿入）／分割統治法（クイック、マージ）／データ構造の利用（ヒープ）
- 降順のヒープソート（親≦子のヒープ、最小値を取り出す）／昇順のヒープソート（親≧子のヒープ）
- シェルソート（間隔を空けて挿入法、改良挿入法）／二分挿入法（挿入位置を2分探索で探す）
- 安全クイックソート（深くなったらヒープソートに切り替える）