クイックソートとは？くいっくそーと
クイックソートとは、基準値（ピボット）を1つ選び、それより小さい要素の集まりと大きい要素の集まりに分割し、各部分に同じ手順を適用して整列する方法。データが増えたときの処理時間の伸び方（計算量）は平均でO(n log n)で実用上非常に速いが、分割が偏ると最悪O(n²)（データ量の2乗に比例して伸びる）になる点が基本情報技術者試験の定番論点。
最終更新：2026-10-09
この語が出る過去問を解く →具体例
[4,1,6,3,5]でピボットに4を選ぶと、[1,3]と[6,5]に分けられ4の位置が確定する。左右それぞれで同じ操作を繰り返せば[1,3,4,5,6]になる。ピボットに中央値に近い値を選べるほど分割が均等になり、分割の段数が少なく済む（データが2倍になっても段数は1段増える程度）。
試験での引っ掛け
「常にO(n log n)」という選択肢は誤り。整列済みデータで端の値をピボットにすると片側が空になり最悪O(n²)。またマージソートと違って作業用の配列がほぼ不要（追加領域が小さい）点、および不安定なソート（同じ値どうしの元の並び順が保たれないことがある整列）である点も問われる。
関連用語
出た過去問
出典：平成30年度 秋期 基本情報技術者試験 午前 問6（IPA）
クイックソートの処理方法を説明したものはどれか。
正解：適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
クイックソートは基準値（ピボット）を選び、それより小さい群と大きい群にデータを分割し、各群に同じ処理を再帰的に適用する分割統治法である。平均計算量はO(n log n)となる。
出典：令和8年度 公開問題 基本情報技術者試験 科目A 問2（IPA）
クイックソートの処理方法を説明したものはどれか。
正解：適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
要点：クイックソートは枢軸で分割し再帰的に整列する
クイックソートは、基準値（枢軸）を選んでデータを基準値より小さい グループ と大きいグループに分割し、各グループに対して同じ操作を再帰的（自分自身を呼び出す形で）に繰り返して整列する方法である。分割統治法（問題を小さく分けて解く考え方）に基づくため平均的な計算量（処理にかかる手間の目安）が小さい。挿入・選択・バブルの各整列法とは考え方が異なる。
出典・参考
公式シラバスの1 基礎理論 ＞ 2. アルゴリズム ＞ (2) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。