整列とは
整列とは、データを決まった順に並べ替える処理で、再帰や分割の仕方によって計算量が変わります。
探索の前にデータを整列すると検索しやすくなりますが、整列自体にも処理時間が必要です。交換や分割の手順から、使うメモリと比較回数を考えます。
基本の仕組み
6、2、8、4を4を基準に分けると、小さい側は2、大きい側は6、8です。それぞれをさらに整列して結ぶと2、4、6、8になります。このように基準値で分割するのがクイックソートの考え方です。
クイックソートは平均的にはO(n log n)ですが、分割が極端に偏るとO(n²)になります。マージソートは部分列を整列して併合し、一般的な配列実装では作業領域を使います。バブルソートは隣接要素を比較・交換するため、多数の比較が必要です。
再帰は自分と同じ処理を小さい問題へ適用する方法です。階乗ならf(0)=1を終了条件にf(n)=n×f(n−1)とします。終了条件だけでなく、そこへ近づく引数の更新が必要で、呼出しの情報はスタックへ積まれます。
整列・再帰の費用
バブル・選択・挿入ソートは基本形の最悪計算量がO(n²)です。マージソートはO(n log n)で補助領域を使い、ヒープソートもO(n log n)です。クイックソートは平均O(n log n)でも、分割が偏ると最悪O(n²)です。再帰は停止条件と呼出しごとの状態を確認します。
| 方法 | 計算量の目安 |
|---|---|
| バブル・選択・挿入 | 最悪O(n²) |
| マージ | O(n log n) |
| ヒープ | O(n log n) |
| クイック | 平均O(n log n)、最悪O(n²) |
試験に出る
- クイックソートは平均O(n log n)だが分割が偏るとO(n²)。
- マージソートは併合で整列し、配列実装では作業領域を使う点。
- バブルソートは隣接比較・交換で比較回数が多いこと。
- 再帰は終了条件と、そこへ近づく引数の更新の両方が必要。
- 再帰呼出しの情報がスタックに積まれること。
重要な言葉
- クイックソート
- 基準値で分割しながら整列する方法。
- マージソート
- 部分列を整列して併合する方法。
- 再帰呼出し
- 自分と同じ処理をより小さい問題へ呼び出すこと。
- 計算量
- 処理に必要な手間を要素数との関係で表した量。
確認問題
確かめようクイックソートはどんな入力でもO(n log n)？
いいえ。分割の偏りによる最悪の場合と、平均的な場合を分けます。
クイックソートは、どの入力でも必ずO(n log n)である。
再帰には終了条件と、そこへ近づく引数の更新が必要。
分割が極端に偏るとO(n²)になる整列法は？
再帰呼出しの情報が積まれる場所は？
探索の前にデータを整列すると検索しやすくなりますが、整列自体にもが必要です。交換や分割の手順から、使うメモリとを考えます。
6、2、8、4を4を基準に分けると、小さい側は2、大きい側は6、8です。それぞれをさらに整列して結ぶと2、4、6、8になります。このようにで分割するのがの考え方です。
クイックソートは平均的にはO(n log n)ですが、分割が極端に偏るとO(n²)になります。は部分列を整列して併合し、一般的な配列実装では作業領域を使います。は隣接要素を比較・交換するため、多数の比較が必要です。
は自分と同じ処理を小さい問題へ適用する方法です。階乗ならf(0)=1をにf(n)=n×f(n−1)とします。終了条件だけでなく、そこへ近づく引数の更新が必要で、呼出しの情報はスタックへ積まれます。
出典・参考資料
試験の公式案内と、この記事の参考にした学習資料です。
編集：Pinternet Works · 更新日：
教材の編集方針・訂正について