基本情報技術者 2011年 春期 午前（科目A） 問08

クイックソートの原理【午前解説】

正解の理由

解法ステップ

1. 各選択肢の記述から、どの整列アルゴリズムの特徴を述べているかを照合する。
2. 「ピボット（基準）を選んで分割し、繰り返す」という語句があるかを確認する。
3. その特徴があるのはクイックソートのみであるため、該当する選択肢が正解となる。

選択肢別の誤答解説

• ア（正答相当）: ピボット選択→パーティション→再帰というクイックソートの本質を述べています。等しい要素の扱い方（左右どちらに入れるか、中間に分ける3-wayなど）は実装差がありますが、定義として正しい記述です。
• イ: 「最も小さい要素を順次取り出す」は選択ソート（Selection Sort）の説明です。選択ソートは選択操作を繰り返して整列しますが、ピボットや分割の概念は含みません。
• ウ: 「取り出した要素を既存の集合に挿入する」は挿入ソート（Insertion Sort）です。逐次的にソート済領域へ挿入していく特徴があります。
• エ: 「隣接要素を比較して逆なら交換する」はバブルソート（あるいは交換ソート系）の説明です。繰り返し隣接比較を行う点が特徴です。

よくある誤解

1. 「クイックソートは常に安定である／安定でない」
   • 安定性は実装に依存します。インプレースなパーティション（典型的なLomuto/Hoare実装）は一般に安定ではありませんが、追加領域を使って元の相対順序を保つように分割すれば安定に実装できます。
2. 「平均計算量が $O(n\log n)$ だから最良の選択」
   • 平均は $O(n\log n)$ ですが、ピボット選択が悪いと最悪 $O(n^2)$ になります。ランダム化や中央値近似（median-of-three）で対策します。
3. 「クイックソートは常にインプレースである」
   • 多くの高速実装はインプレースですが、安定化や関数型スタイルの実装は追加メモリを要します。用途や制約に応じて選びます。

補足コラム

• 計算量: 平均 $O(n\log n)$、最悪 $O(n^2)$（例: 毎回最小または最大をピボットに選ぶ場合）。期待的に高速で、定数因子も小さいため実務で広く使われます。
• ピボット戦略: 先頭・末尾・ランダム・median-of-three など。ランダム化や中央値近似が最悪ケースを防ぎます。
• パーティション方式: Lomuto（簡潔だが一般にやや遅い）、Hoare（高速だが実装注意）、3-way（等値要素が多いときに有効）。
• 安定化: 安定ソートにするには各パーティションを元の出現順で集める実装（追加配列を用いる）にすれば良いです。メモリトレードオフがあります。
• 実用上の工夫: 小さい部分配列は挿入ソートに切り替える（閾値は環境依存）、再帰の深さを制限するなど。

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

def partition(a, lo, hi):
    pivot = a[hi]
    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

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

FAQ