整列アルゴリズムの計算量
n 個のデータを整列するアルゴリズムのうち，平均時間計算量と最悪時間計算量がいずれも O(n log n) であるものはどれか。
- アクイックソート
- イバブルソート
- ウ挿入ソート
- エヒープソート
正解と解説を見る
正解 エ
この問題の基礎知識
- 時間計算量の O 記法は，データ数 n が大きくなったときの処理時間の増え方を表す。平均時間計算量と最悪時間計算量は，入力データの並び方によって異なる場合がある。
- バブルソート，挿入ソート，選択ソートなどの基本的な整列法は，平均・最悪ともに O(n²) である。
- クイックソートは基準値（ピボット）でデータを分割する方式で，平均は O(n log n) だが，分割が偏ると O(n²) になる。マージソートは最悪でも O(n log n) である。
- ヒープは，親の値が子の値以上（又は以下）という条件を満たす完全二分木であり，根の取出しや要素の追加の後の再構成は O(log n) で行える。
アクイックソート
平均時間計算量は O(n log n) であるが，基準値（ピボット）の選び方によっては分割が偏り，最悪時間計算量は O(n²) になる。
イバブルソート
隣接する要素の比較と交換を繰り返す方式であり，平均時間計算量，最悪時間計算量ともに O(n²) である。
ウ挿入ソート
整列済みの部分列に要素を挿入していく方式であり，ほぼ整列済みのデータでは高速だが，平均・最悪時間計算量はともに O(n²) である。
エヒープソート正解
データをヒープ構造に構成し，最大（最小）値の取出しと再構成を繰り返す。再構成が O(log n) で済むため，平均・最悪ともに O(n log n) である。
検証用の出典出典照合済み
JIS X 0001 情報処理用語（基本用語） ／ NIST Dictionary of Algorithms and Data Structures照合の根拠（4 件）
- エ（正解）: ヒープを構築して最大値の取出しを繰り返し，実行時間は O(n log n)（上界なので最悪時も O(n log n)）
A sort algorithm that builds a heap, then repeatedly extracts the maximum item. Run time is O(n log n).
NIST Dictionary of Algorithms and Data Structures · heapsort (Definition)（新しいタブで開きます） - ア（誤り）: クイックソートは通常 O(n log n) だが最悪時は Θ(n²)
Quicksort has running time Θ(n²) in the worst case, but it is typically O(n log n).
NIST Dictionary of Algorithms and Data Structures · quicksort (Note)（新しいタブで開きます） - イ（誤り）: 隣接要素の比較・交換を繰り返すバブルソートは任意のデータで O(n²)
Complexity is O(n 2 ) for arbitrary data, but approaches Θ(n) if the list is nearly in order at the beginning.
NIST Dictionary of Algorithms and Data Structures · bubble sort (Note)（新しいタブで開きます） - ウ（誤り）: 整列済み部分に挿入していく挿入ソートの実行時間は O(n²)
Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted. Run time is O(n 2 ) because of moves.
NIST Dictionary of Algorithms and Data Structures · insertion sort (Definition)（新しいタブで開きます）
NIST DADS（xlinux.nist.gov）で各整列法の定義と計算量を確認した。