BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
クイックソート
基準値で分けて整列する
クイックソートは、基準となる値を選び、それより小さい側と大きい側に分割して、それぞれを整列する方法です。基準値をピボットと呼びます。分割した部分にも同じ考え方を繰り返すため、分割統治法の例になります。配列の中で要素を交換する実装など、さまざまな変種があります。
学習用の実装例
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件クイックソート
基準値で分けて整列する クイックソートは、基準となる値を選び、それより小さい側と大きい側に分割して、それぞれを整列する方法です。基準値をピボットと呼び...
クラスタ分析
クラスタとは、「cluster」という英語からきた言葉で、「固まり、群れ、房」という意味があります。つまり、クラスタ分析とは、様々なものが混ざりあっている集...
クリックジャッキング
見えている操作と実際の操作をずらす クリックジャッキングは、利用者が押していると思ったものとは別のボタンなどを操作させる攻撃です。正規のページを透明な...
クロスサイトスクリプティング
ページに不正な処理が混ざる クロスサイトスクリプティングは、Webページへ出力されるデータの扱いに不備があり、攻撃者の意図するスクリプトなどが利用者のブラ...