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

クイックソートの分割手法【午前解説】

正解の理由

解法ステップ

1. 文中のキーワードを確認：「基準値」「小さい値のグループと大きい値のグループに分割」「繰り返す」──これらはクイックソートの特徴。
2. 他の選択肢と対応付け：
   • 「既に整列済みのデータ列に追加する」は挿入法（Insertion Sort）。
   • 「最小値を逐次取り出す」は選択法（Selection Sort）。
   • 「隣接要素を比較して入替え、小さいものを端に移す」はバブルソート。
3. よって「基準値で分割して再帰的に整列する」選択肢がクイックソートに該当する。

選択肢別の誤答解説

• ア: 挿入法（Insertion Sort）
  既に整列済みの部分列に要素を挿入して拡張していく方法。安定で小規模またはほぼ整列済みの配列に有利。アルゴリズムの分割統治的な分配・再帰は含まれない。
• イ: 選択法（Selection Sort）
  配列から最小（または最大）を探して先頭に置き、それを除いて同様の操作を繰り返す手法。探索と交換を繰り返すため要素の移動が相対的に少ないが、一般的には安定ではない（工夫で安定化可能）。
• ウ: クイックソート（正解）
  ピボット選択→パーティション→再帰的整列の流れ。平均計算量は $O(n\log n)$、最悪は $O(n^2)$（ピボットが極端に偏る場合）。
• エ: バブルソート（Bubble Sort）
  隣接要素を比較・交換して小さい要素を徐々に前に移す手法。実装は単純だが効率は低く、平均・最悪とも $O(n^2)$。

よくある誤解

1. 「クイックソートは常に不安定（安定でない）」
   → 一般に用いられるインプレースなパーティション方式（Lomuto, Hoare など）による実装は安定でないことが多いが、配列を分割して新しいリストを作る単純な再帰実装（例：less/equal/greater を使う実装）は元配列の順序を保持するため安定になります。実装の方法で安定性は変わります。
2. 「クイックソートは必ず高速」
   → 平均では高速（$O(n\log n)$）ですが、ピボット選択が悪いと最悪 $O(n^2)$ になります。ランダム化や中央値選択で最悪事態を避ける工夫が重要です。

補足コラム

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)

• 平均計算量: $O(n\log n)$
• 最悪計算量: $O(n^2)$（偏ったピボット）
• 追加領域: 実装次第（非インプレース版は $O(n)$、インプレース版は平均 $O(\log n)$ の再帰深さ）

FAQ