基本情報技術者 2026年 科目A 問02

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

正解の理由

解法ステップ

1. 各選択肢のキーワードを探す（例：「基準値」「分割」「繰り返す」「隣り合った比較」など）。
2. キーワードを既知のソートアルゴリズムに対応付ける：
   • 「基準値」「分割」→ クイックソート
   • 「正しい位置に追加」→ 挿入ソート
   • 「最小値を順に取り出す」→ 選択ソート
   • 「隣接比較と入替えで端に移す」→ バブルソート
3. キーワードと一致する記述を選ぶ（今回は ウ が一致）。

選択肢別の誤答解説

• ア: 挿入ソート（Insertion Sort）の説明です。既に整列済みの部分列に新しい要素を適切な位置へ挿入していく手法で、平均・最悪共に $O(n^2)$、小規模またはほぼ整列済みの場合に高速です。よってクイックソートではない。
• イ: 選択ソート（Selection Sort）の説明です。配列から最小値（または最大値）を順に選んで確定させていく手法で、比較回数は常に $O(n^2)$。これもクイックソートではありません。
• ウ: クイックソートの典型的な説明です。基準（ピボット）で分割して再帰的にソートする点が一致します。
• エ: バブルソート（Bubble Sort）の説明です。隣接要素を比較して入れ替える操作を繰り返し、徐々に大きい（あるいは小さい）要素を端へ移動させる手法。単純だが非効率で $O(n^2)$。

よくある誤解

1. 「分割している＝マージソート」と混同する
   • 両者とも分割統治だが、クイックソートは分割後の結合処理がほぼ不要（部分配列を単に結合）で、マージソートは分割後にマージ処理が必要。挙動や安定性が異なります。
2. 「クイックソートは常に高速」と考える誤り
   • 平均は高速だが、不適切なピボット選択（常に最小/最大を選ぶ等）では最悪 $O(n^2)$ になるため、ピボット戦略が重要です。
3. 「クイックソートは安定である」との誤解
   • 一般的なクイックソートは安定ではありません（同値の要素の相対順序が保持されない）。

補足コラム

• パーティション手法の代表例：
  • Hoareの分割法：比較的高速で交換回数が少ない。インデックスを両端から移動して交換する。
  • Lomutoの分割法：実装が簡単だが交換回数が多く効率はやや劣る。
• 実装上の工夫：
  • ピボットをランダムに選ぶ、または中央値（median-of-three）を使うことで最悪ケースを避けやすい。
  • 深さが深くなりすぎる場合はヒープソートに切り替える（introsort）ことで最悪計算量を改善する実装もある。
• 簡単な再帰的実装例（説明用、安定性・最適化未考慮）：

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

FAQ