過去問クラブ 学ぶ、わかる、つづく。
ログイン
用語解説

クイックソート

基準値で分けて整列する

クイックソートは、基準となる値を選び、それより小さい側と大きい側に分割して、それぞれを整列する方法です。基準値をピボットと呼びます。分割した部分にも同じ考え方を繰り返すため、分割統治法の例になります。配列の中で要素を交換する実装など、さまざまな変種があります。

学習用の実装例

def quick_sort(values):
    if len(values) <= 1:
        return values
    pivot = values[len(values) // 2]
    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    upper = [value for value in values if value > pivot]
    return quick_sort(lower) + equal + quick_sort(upper)

考え方を示すため、別の配列を作る例です。実用的なその場での分割とは記憶量が異なります。同じ値を別に集めることで、等しい要素の扱いを明確にしています。

分割の偏り

均等に近く分かれれば、各段階で全体を調べる処理を対数程度の段数で行えます。平均的にはO(n log n)ですが、一方が極端に小さい分割が続くとO(n²)になる場合があります。ピボットの選び方や同じ値が多いデータへの対応が重要です。名前に「クイック」とあるから常に最速とは限りません。

安定性と記憶量

典型的な交換による実装は安定な整列とは限らず、同じキーを持つ要素の元の順序が変わることがあります。また、その場で分割しても再帰呼出しの情報は必要です。補助配列を使う例と、配列内で交換する例を混同して記憶量を答えないようにします。

試験で追う操作

問題によってピボットの位置、左右から走査する方向、等しい値の扱いが異なります。一般的な名前だけで交換順序を決めず、提示された手順を一つずつ追います。分割が終わった時点で、左右の各部分はまだ完全に整列していないことがあります。「ピボットを基準に分かれた状態」と「全体の整列完了」を区別することが重要です。

参考資料

内容確認日:2026-11-13

この言葉を含む問題を探す

この用語に関連する問題

1問

用語一覧

4件