アルゴリズムとプログラミングアルゴリズムとデータ構造

n 個のデータをソートするとき、最悪計算量が O(n²) となるソートアルゴリズムはどれか。

ア.マージソート

イ.ヒープソート

ウ.クイックソート正解

エ.基数ソート

解説

クイックソートは平均は速いが、運悪くピボットが端っこばかり選ばれると一気に O(n²) に転落する「気分屋」アルゴリズムです。

なぜウが正解か

クイックソートの最悪計算量は O(n²)。すでにソート済み配列に対して「常に先頭をピボットにする」素朴な実装だと、分割が片寄って n 段の再帰になり 1+2+…+n ≈ n²/2 回の比較が発生します。平均は O(n log n) なのに最悪が O(n²) という落差が、まさにクイックソートのキャラクターです。

なぜアは間違いか

マージソートは入力に依存せず常に O(n log n)。安定して速いが追加メモリ O(n) を必要とするのが弱点で、計算量で破綻することはありません。

なぜイは間違いか

ヒープソートも常に O(n log n)。最悪計算量を抑えたい場面で選ばれる、優等生タイプの比較ソートです。

なぜエは間違いか

基数ソートは比較を使わず桁ごとに分配するので O(d×(n+k))（d=桁数、k=基数）。比較ソートの O(n log n) 下限すら超えてくる別系統で、n² にはなりません。

出典: AI生成問題（学習用）

← 前の問題

グラフの探索アルゴリズムである幅優先探索（BFS）と深さ優先探索（DFS）の説明として、最も適切なものはどれか。

次の問題 →

ソート済みの n 個のデータに対して二分探索を行うときの、最悪計算量はどれか。

アルゴリズムとプログラミングの問題を解くこの分野の問題一覧を見る