クイックソートとは？

クイックソートの意味

基準値（ピボット）を1つ選び、それより小さい要素の集まりと大きい要素の集まりに分割し、各部分に同じ手順を適用して整列する方法。平均計算量はO(n log n)で実用上非常に速いが、分割が偏ると最悪O(n²)になる点がFEの定番論点。

クイックソートの具体例

[4,1,6,3,5]でピボットに4を選ぶと、[1,3]と[6,5]に分けられ4の位置が確定する。左右それぞれで同じ操作を繰り返せば[1,3,4,5,6]になる。ピボットに中央値に近い値を選べるほど分割が均等になり、深さがlog n程度に収まる。

クイックソートは試験でどう引っ掛けられる？

「常にO(n log n)」という選択肢は誤り。整列済みデータで端の値をピボットにすると片側が空になり最悪O(n²)。またマージソートと違って作業用の配列がほぼ不要（追加領域が小さい）点、および不安定なソートである点も問われる。

クイックソートと関連する用語

• クイックソート・マージソート・ヒープソート
• 安定ソート

クイックソートが出た過去問

• アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。

  正解：全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。

  要点：分割統治法は小問題に分けて解き結果を統合する

  分割統治法は、解きにくい大きな問題を同じ構造の小さな部分問題に分割し、それぞれを独立に解いてから結果を統合して元の問題の解を得る手法である。マージソートやクイックソート、二分探索などが代表例で、再帰的に分割していく点が特徴である。

  出典：令和3年度 春期 高度共通_午前I試験 am1 問3（IPA）

• 配列に格納されたデータ2, 3, 5, 4, 1に対して、クイックソートを用いて昇順に並べ替える。2回目の分割が終わった状態はどれか。ここで、分割は基準値より小…

  正解：1, 2, 3, 5, 4

  要点：クイックソートは基準値の前後に振り分ける操作を再帰的に繰り返す

  1回目は左端の2を基準に、より小さい1と、より大きい3・5・4に分けるので並びは1, 2, 3, 5, 4となる。2回目は右側のグループ3, 5, 4を左端の3を基準に分割するが、3より小さい要素がないため3の位置は動かず、5・4がそのまま右側に残る。よって配列全体は1, 2, 3, 5, 4のままである。

  出典：令和5年度 春期 高度共通_午前I試験 am1 問3（IPA）