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

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

要点まとめ

• 結論：クイックソートは基準値（ピボット）で配列を小さいグループと大きいグループに分割し、再帰的に並べ替える分割統治法です。
• 根拠：各分割（パーティション）で要素を左右に振り分け、その後それぞれを独立にソートするため平均時間計算量は $O(n\log n)$ となります。
• 差がつくポイント：ピボットの選び方とパーティション手法で最悪計算量や実行時間が大きく変わるため、ランダム化や median-of-three、閾値で挿入ソートへ切替える工夫を覚えておくと有利です。

正解の理由

よくある誤解

• クイックソートは常に速いと思われがちですが、最悪ケースでは $O(n^2)$ になる点を誤解しやすいです。
• 安定なソートだと勘違いされることがあるが、標準実装は不安定です。

解法ステップ

1. 問題文のキーワードを探す：「基準値」「分割」「同様にして…繰り返す」などの語がクイックソートを示唆します。
2. 各選択肢のアルゴリズム特徴を対応づける：挿入ソート、選択ソート、クイックソート、バブルソートを照合します。
3. クイックソート特有の「パーティション＋再帰」を含む選択肢を選ぶ。ウが該当します。
4. 補足で計算量や安定性を確認して、誤答の原因を整理します。

選択肢別の誤答解説

• ア: 既に整列済みの位置に順に挿入する操作の繰り返しは「挿入ソート（Insertion Sort）」の説明であり、クイックソートではありません。
• イ: 毎回最小値を取り出していく説明は「選択ソート（Selection Sort）」で、各ステップで最小（または最大）を選ぶ手法です。
• ウ: 基準値で分割し再帰的に処理する説明はクイックソートそのもので、正解です。
• エ: 隣接要素の比較と交換を繰り返して値を端に移す方法は「バブルソート（Bubble Sort）」の説明で、異なるアルゴリズムです。

補足コラム

• 計算量：平均 $O(n\log n)$、最悪 $O(n^2)$（偏ったピボット選択時）。
• 安定性：基本実装は不安定。安定化には追加処理や別手法が必要です。
• パーティション手法：Hoare方式（効率的で交換回数が少ない）と Lomuto方式（実装が単純だが交換多め）が有名です。
• 実用的最適化：ランダムピボット、median-of-three、部分配列が小さい場合は挿入ソートへ切替える、尾再帰最適化などがあります。
• 実装例（簡易、再帰的）：

def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = partition(a, lo, hi)
        quicksort(a, lo, p-1)
        quicksort(a, p+1, hi)

def partition(a, lo, hi):
    pivot = a[hi]  # Lomuto
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

FAQ