基本情報技術者 2018年 秋期 午前（科目A） 問06

クイックソートの処理方法を説明したものはどれか。【午前2 解説】

要点まとめ

• 結論→クイックソートは基準値（ピボット）で配列を「小さい群」と「大きい群」に分割し、それぞれを再帰的に分割して整列するアルゴリズムです。
• 根拠→各分割でピボットが最終位置に固定され、分割統治で部分問題を解くため平均計算量は $O(n\log n)$、最悪は $O(n^2)$ になります。
• 差がつくポイント→ピボットの選び方やパーティション実装（インプレース／安定性）で実行速度や空間効率に大きな差が出る点を押さえてください。

正解の理由

よくある誤解

• ピボットは必ず中央値を選ぶ必要がある：中央値を選べば理想的ですが、アルゴリズム上は任意の要素をピボットにできます。ランダム化や中央値近似で性能改善します。
• クイックソートは常に高速：平均は高速ですが、ピボット選択が悪いと最悪計算量 $O(n^2)$ になります。実装で対策が必要です。
• クイックソートは安定ソートである：多くの一般的な実装は安定ではなく、同値要素の相対順序は保証されません。

解法ステップ

1. 問題文を読み、キーとなる語句（基準値、分割、再帰）を探す。
2. 「基準値で分割して再帰的に処理する」という特徴が書かれている選択肢を選ぶ。
3. 他の選択肢が別のソート（挿入、選択、バブル等）を説明していないか照合する。
4. 正答を確認して、ピボットや計算量に関する補足を頭に入れる。

選択肢別の誤答解説

• ア: 「既に整列済みのデータ列の正しい位置に、データを追加する操作を繰り返す方法」→ これは挿入ソートの説明で、既存部分が整列済みでそこに新要素を挿入していく手法です。
• イ: 「データ中の最小値を求め、次にそれを除いた部分の中から最小値を求める」→ これは選択ソート（選択法）の説明で、毎回最小（または最大）を選んで確定させる方式です。
• ウ: 「適当な基準値を選び、それよりも小さな値のグループと大きな値のグループにデータを分割する。…」→ これがクイックソートの定義です（正答）。
• エ: 「隣り合ったデータの比較と入替えを繰り返すことによって、小さな値のデータを次第に端の方に移していく方法」→ これはバブルソートの説明で、隣接要素の交換を繰り返す手法です。

補足コラム

• 計算量：平均 $O(n\log n)$、最悪 $O(n^2)$。最悪は例えばすでに整列済み配列で先頭や末尾をピボットに固定すると発生します。
• 空間計算量：一般にインプレース実装で平均追加空間は $O(\log n)$（再帰深さ）、ピボット選択や安定化のために追加配列を使うと $O(n)$ になることもあります。
• 改良策：ランダムピボット、中央値（median-of-three）選択、再帰深度が深くなったらヒープソートへ切替える（イントロソート）等の手法で最悪ケースを回避できます。
• 安定性：標準的なクイックソートは安定ではないため、安定性が必要ならマージソートなど別アルゴリズムを検討します。

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quicksort(less) + equal + quicksort(greater)

FAQ