クイックソートとは？

クイックソートの意味

基準値（ピボット）を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²)。またマージソートと違って作業用の配列がほぼ不要（追加領域が小さい）点、および不安定なソートである点も問われる。

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

• マージソート
• ヒープソート
• 安定ソート

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

• クイックソートの処理方法を説明したものはどれか。

  正解：適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。

  要点：クイックソートは基準値で二分し再帰する分割統治法

  クイックソートは基準値（ピボット）を選び、それより小さい群と大きい群にデータを分割し、各群に同じ処理を再帰的に適用する分割統治法である。平均計算量はO(n log n)となる。

  出典：平成30年度 秋期 基本情報技術者試験 午前 問6（IPA）

• クイックソートの処理方法を説明したものはどれか。

  正解：適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。

  要点：クイックソートは枢軸で分割し再帰的に整列する

  クイックソートは、基準値（枢軸）を選んでデータを基準値より小さい グループ と大きいグループに分割し、各グループに対して同じ操作を再帰的に繰り返して整列する方法である。分割統治法に基づくため平均的な計算量が小さい。挿入・選択・バブルの各整列法とは考え方が異なる。

  出典：令和8年度 （公開問題） 基本情報技術者試験 kamokuA 問2（IPA）