応用情報技術者 2019年 秋期 午前2 問08

分割統治による整列【午前2解説】

正解の理由

解法ステップ

1. 「分割統治」の定義を確認する：分割 → 再帰的解決 → 結合の3段階があるかを基準にする。
2. 各選択肢のアルゴリズムの基本動作を思い出す：分割して再帰的に処理するか、逐次的に処理するか。
3. 分割して再帰的に処理するものを選ぶ：これが分割統治を採用しているアルゴリズムである。
4. それに当てはまるのがクイックソートであるため、イを選ぶ。

選択肢別の誤答解説

• ア: 基数ソート
  • 基数ソートは桁ごとに安定な並べ替え（バケット化）を行う非比較ソートで、分割統治の「分割→再帰→結合」という形態ではない。入力を桁単位で処理する逐次的な手順であるため不適。
• イ: クイックソート
  • パーティションで分割し、各部分を再帰的にソートするため分割統治法の代表例。これが正解である。
• ウ: 選択ソート
  • 配列から順に最小（または最大）を選んで先頭に置く逐次選択型のアルゴリズムで、分割して再帰的に処理する形ではない。
• エ: 挿入ソート
  • 部分列を逐次拡張してソートする逐次挿入型のアルゴリズムで、分割統治法とは異なる（小さい入力で有効だが再帰的分割は行わない）。

よくある誤解

• 「分割して結合すればそれは分割統治」→ 単に分割するだけでなく、分割後に再帰的に処理し適切に結合することが重要です。例えば基数ソートは分割的に見える工程があっても分割統治の枠組みとは異なります。
• 「高速＝分割統治」→ 分割統治法は平均で高速になることが多いですが、最悪計算量が悪化する場合（クイックソートの最悪は $O(n^2)$）もあり、常に最適とは限りません。

補足コラム

• クイックソートの計算量は平均で $O(n\log n)$、最悪で $O(n^2)$（ピボット選択が悪い場合）。実装次第で in-place（追加メモリほぼ不要）で高速に動くため実用上よく使われます。
• 安定性：標準的なクイックソートは安定ではありません（同じキーの相対順序を維持しない）。安定な $O(n\log n)$ ソートとしてはマージソートが知られています（ただし追加領域を必要とする）。
• 実装上の工夫：ランダムピボットや三分割（Dutch national flag）パーティション、末尾再帰の最適化、小さい部分に対して挿入ソートへ切り替えるなどで実行速度/安定性/最悪ケース対策が改善されます。

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    mid  = [x for x in arr if x == pivot]
    right= [x for x in arr if x > pivot]
    return quicksort(left) + mid + quicksort(right)

FAQ