クイックソート・マージソート・ヒープソートとは？
クイックソート・マージソート・ヒープソートとは、高速な整列アルゴリズムの代表例で、平均計算量はいずれもO(n log n)。クイックソートは基準値（ピボット）より小さい要素・大きい要素に分割して再帰的に整列、マージソートはデータを分割してそれぞれ整列した後に併合（マージ）、ヒープソートは木構造の一種であるヒープを利用して最大値・最小値を順に取り出す。
基本情報技術者試験の過去問では2回出題されています（2018年度〜2026年度）。
くいっくそーと・まーじそーと・ひーぷそーと
クイックソート・マージソート・ヒープソートの意味
高速な整列アルゴリズムの代表例で、平均計算量はいずれもO(n log n)。クイックソートは基準値（ピボット）より小さい要素・大きい要素に分割して再帰的に整列、マージソートはデータを分割してそれぞれ整列した後に併合（マージ）、ヒープソートは木構造の一種であるヒープを利用して最大値・最小値を順に取り出す。
クイックソート・マージソート・ヒープソートの具体例
クイックソートはピボットの選び方が悪い（すでに整列済みのデータで先頭を毎回ピボットに選ぶなど）と最悪計算量O(n²)に悪化する場合がある一方、平均的には非常に高速で実用上よく使われる。
クイックソート・マージソート・ヒープソートは試験でどう引っ掛けられる？
バブルソート等（O(n²)）とクイックソート等（平均O(n log n)）の計算量の違い、およびクイックソートの最悪計算量がO(n²)になり得る点が問われやすい。
クイックソート・マージソート・ヒープソートと関連する用語
クイックソート・マージソート・ヒープソートが出た過去問
クイックソートの処理方法を説明したものはどれか。
正解：適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
要点：クイックソートは基準値で二分し再帰する分割統治法
クイックソートは基準値（ピボット）を選び、それより小さい群と大きい群にデータを分割し、各群に同じ処理を再帰的に適用する分割統治法である。平均計算量はO(n log n)となる。
出典：平成30年度 秋期 基本情報技術者試験 午前 問6（IPA）クイックソートの処理方法を説明したものはどれか。
正解：適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
要点：クイックソートは枢軸で分割し再帰的に整列する
クイックソートは、基準値（枢軸）を選んでデータを基準値より小さい グループ と大きいグループに分割し、各グループに対して同じ操作を再帰的に繰り返して整列する方法である。分割統治法に基づくため平均的な計算量が小さい。挿入・選択・バブルの各整列法とは考え方が異なる。
出典：令和8年度 （公開問題） 基本情報技術者試験 kamokuA 問2（IPA）
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。