クイックソートとは？くいっくそーと
クイックソートとは、基準値（ピボット）を選び、それより小さい要素の群と大きい要素の群へ分割してから、各群へ同じ手順を再帰的に適用する整列法。平均計算量はO(n log n)で定数因子も小さいが、分割が偏ると最悪O(n²)まで劣化するため、実行時間の上限を保証できないという性質を併せ持つ。
最終更新：2026-10-06
エンベデッドSPを最短で暗記・合格する →背景
整列は追加のメモリ・平均速度・最悪速度の綱引きで、どれか1つが万能ということはない。クイックソートは配列の中で入れ替えを済ませて追加領域をほとんど使わない代わりに、最悪ケースを引き受ける設計になっている。最悪実行時間が要件になる領域では、この引き換えを許容できるかどうかが選定の分かれ目になる。
具体例
[4,1,6,3,5]でピボットに4を選べば[1,3]と[6,5]に分かれ、4の位置が確定する。組込みで先に効いてくるのは速度より再帰の深さで、偏った入力では段数がnに近づきタスクスタックを食い潰す。件数が少なく既知なら挿入ソート、最悪値の保証が要るならヒープソート、という選び方になる。
試験での引っ掛け
「常にO(n log n)」とする選択肢は誤りで、整列済みの列に端の値をピボットを取ると片側が空になり最悪O(n²)。同じ値の順序が保たれない不安定なソートである点、マージソートと違って作業用の領域がほぼ不要な点も対比で問われる。ハードリアルタイムの区間で使うなら最悪時間の見積りが要る。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。