クイックソート・マージソート・ヒープソートとは？

クイックソート・マージソート・ヒープソートの意味

高速な整列アルゴリズムの代表例で、平均計算量はいずれもO(n log n)。クイックソートは基準値（ピボット）より小さい要素・大きい要素に分割して再帰的に整列、マージソートはデータを分割してそれぞれ整列した後に併合（マージ）、ヒープソートは木構造の一種であるヒープを利用して最大値・最小値を順に取り出す。

クイックソート・マージソート・ヒープソートの具体例

クイックソートはピボットの選び方が悪い（すでに整列済みのデータで先頭を毎回ピボットに選ぶなど）と最悪計算量O(n²)に悪化する場合がある一方、平均的には非常に高速で実用上よく使われる。

クイックソート・マージソート・ヒープソートは試験でどう引っ掛けられる？

バブルソート等（O(n²)）とクイックソート等（平均O(n log n)）の計算量の違い、およびクイックソートの最悪計算量がO(n²)になり得る点が問われやすい。

クイックソート・マージソート・ヒープソートと関連する用語

• 整列アルゴリズム（バブルソート・選択ソート・挿入ソート）
• 計算量とO記法（オーダ記法）
• 木構造（二分木）

クイックソート・マージソート・ヒープソートが出た過去問

• ヒープソートの説明として、適切なものはどれか。

  正解：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。

  要点：ヒープソートは順序木から最小値を取り出し続ける

  ヒープソートは、未整列部分を親子の大小関係が保たれた順序木（ヒープ）として構成し、根にある最小値（または最大値）を取り出して整列済み部分へ移す操作を繰り返す。取り出すたびにヒープを再構成するため、計算量は最悪でもO(n log n)に収まる。

  出典：平成28年度 秋期 高度共通_午前I試験 am1 問3（IPA）

• アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。

  正解：全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。

  要点：分割統治法は小問題に分けて解き結果を統合する

  分割統治法は、解きにくい大きな問題を同じ構造の小さな部分問題に分割し、それぞれを独立に解いてから結果を統合して元の問題の解を得る手法である。マージソートやクイックソート、二分探索などが代表例で、再帰的に分割していく点が特徴である。

  出典：令和3年度 春期 高度共通_午前I試験 am1 問3（IPA）

• 配列に格納されたデータ2, 3, 5, 4, 1に対して、クイックソートを用いて昇順に並べ替える。2回目の分割が終わった状態はどれか。ここで、分割は基準値より小…

  正解：1, 2, 3, 5, 4

  要点：クイックソートは基準値の前後に振り分ける操作を再帰的に繰り返す

  1回目は左端の2を基準に、より小さい1と、より大きい3・5・4に分けるので並びは1, 2, 3, 5, 4となる。2回目は右側のグループ3, 5, 4を左端の3を基準に分割するが、3より小さい要素がないため3の位置は動かず、5・4がそのまま右側に残る。よって配列全体は1, 2, 3, 5, 4のままである。

  出典：令和5年度 春期 高度共通_午前I試験 am1 問3（IPA）