整列アルゴリズムの計算量比較とは？

整列アルゴリズムの計算量比較とは、各整列法の速さをオーダ記法で押さえる論点。バブル・選択・挿入は平均も最悪もO(n²)、マージとヒープは平均も最悪もO(n log n)、クイックは平均O(n log n)だが最悪はO(n²)になる。FEでは、この表を根拠にした選択問題が繰り返し出る。

せいれつあるごりずむのけいさんりょうひかく

基本情報技術者試験の頻出用語／テクノロジ系

整列アルゴリズムの計算量比較の意味

各整列法の速さをオーダ記法で押さえる論点。バブル・選択・挿入は平均も最悪もO(n²)、マージとヒープは平均も最悪もO(n log n)、クイックは平均O(n log n)だが最悪はO(n²)になる。FEでは、この表を根拠にした選択問題が繰り返し出る。

要素数が1,000から10,000へ10倍になると、O(n²)の手法は所要時間がおよそ100倍に膨らむが、O(n log n)の手法は十数倍で済む。データ量が増えるほど、オーダの差が実行時間の差として効いてくる。

クイックソートは平均は最速級だが、既に整列済みのデータで基準値の選び方が悪いと最悪O(n²)になる点が頻出。またオーダは定数倍を無視するので、少数データでは単純な挿入法のほうが速いこともある。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。