基本情報技術者 2015年秋期午前（科目A）問07

問題文

整列アルゴリズムの一つであるクイックソートの記述として、適切なものはどれか。

選択肢

ア：対象集合から基準となる要素を選び、これよりも大きい要素の集合と小さい要素の集合に分割する。この操作を繰り返すことによって、整列を行う。（正解）

イ：対象集合から最も小さい要素を順次取り出して、整列を行う。

ウ：対象集合から要素を順次取り出し、それまでに取り出した要素の集合に順序関係を保つよう挿入して、整列を行う。

エ：隣り合う要素を比較し、逆順であれば交換して、整列を行う。

##: クイックソートの記述【午前2 解説】

要点まとめ

結論→クイックソートは分割統治法を用い、配列からピボットを選んで大小に分割し再帰的に整列するアルゴリズムです。
根拠→各分割操作（パーティション）はピボットより小さい集合と大きい集合を作るため、部分問題を独立に解くことで全体が整列されます。
差がつくポイント→平均計算量は $O (n lo g n)$ だがピボット選択次第で最悪 $O (n^{2})$ 、不安定である点を覚えて差を付けます。

正解の理由

正解はアです。選択肢アは「基準（ピボット）を選び、それより大きい要素と小さい要素に分割し繰り返す」と記述しており、クイックソートの本質的手順である「ピボットによるパーティション分割」と「分割した部分に再帰的に同じ操作を適用する」ことを正しく表しています。これにより最終的に全体が整列されます。

よくある誤解

「ピボットで分割する」と「順次最小要素を取り出す」は混同しやすく、前者がクイックソート、後者が選択ソートである点を取り違えます。
安定性について「クイックソートは安定だ」と誤解されがちですが、標準実装は安定ではありません（同値要素の順序を保証しない）。

解法ステップ

記述文のキーワードに注目する：ピボット、分割、再帰、部分集合などがあるか確認します。
「最も小さい要素を順次取り出す」は選択ソート、「要素を取り出して既存列に挿入」は挿入ソート、「隣り合う要素を比較し交換」はバブルソートと対応付けます。
キーワードが「ピボットで分割」ならクイックソートと断定し、該当選択肢を正解とします。

選択肢別の誤答解説

ア: 正解。ピボットを使って配列を小さい集合と大きい集合に分割し、再帰的に整列する手法を正確に述べています。
イ: 誤り。これは「選択ソート（Selection Sort）」の記述であり、配列から最小（または最大）を繰り返し取り出す手順です。
ウ: 誤り。これは「挿入ソート（Insertion Sort）」の説明で、順次要素を取り出して既に整列した部分列に挿入する手順です。
エ: 誤り。これは「バブルソート（Bubble Sort）」の説明で、隣接要素を比較して逆なら交換する操作を繰り返すアルゴリズムです。

補足コラム

クイックソートは平均計算量

O (n lo g n)

、最悪計算量

O (n^{2})

（既に整列済や偏ったピボット選択で発生）で、インプレースに実装可能なためメモリ効率が良い利点があります。ピボット選択（中央値選択やランダム化）や三分割パーティショニング（等しい要素群を分ける）を組み合わせると実用上の性能と安定性課題を緩和できます。比較ベースのソートでは最良に近い実用性を持つため多くのライブラリで採用されていますが、標準実装では安定性が必要な場面では安定ソート（マージソート等）を選びます。

FAQ

Q: クイックソートは安定ですか？
A: 標準的なクイックソートは安定ではありません。同値要素の入力順序を保持しないため、安定性が必要ならマージソート等を検討してください。

Q: 最悪ケースはいつ起きますか？
A: 毎回極端なピボット（最小または最大）が選ばれると、分割が片寄り

O (n^{2})

となります。ランダム化や中央値選択で回避できます。

Q: クイックソートとマージソート、どちらが良いですか？
A: 一般にクイックソートは平均で高速かつメモリ効率が良いが、最悪ケースと安定性の点でマージソートには劣ります。用途に応じて選択してください。

関連キーワード: クイックソート、ピボット、分割統治法、パーティション、平均計算量、最悪計算量、安定性、選択ソート、挿入ソート、バブルソート

← 前の問題へ次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！