クイックソートとは？

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

くいっくそーと

エンベデッドシステムスペシャリスト試験の頻出用語／午前II

クイックソートの意味

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

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。