日本語
メニュー

データ構造とアルゴリズム

最悪の場合でも計算量が O(n log n) で、作業用の配列などの追加の記憶領域をほとんど使わずに並べ替えられるソートはどれか。

  1. Aマージソート
  2. Bヒープソート
  3. Cクイックソート
答えと解説を見る

正解：B. ヒープソート

ヒープソートは、配列の中に二分ヒープを作り、根の最大値を末尾と交換してヒープを縮めることを繰り返すので、最悪でも O(n log n) で、追加の領域は定数で済みます。マージソートも最悪 O(n log n) ですが、配列で行うには作業用に n に比例する領域が必要です。クイックソートは平均 O(n log n) で実際には速いものの、ピボットの選び方とデータによっては O(n²) になります。なお、ヒープソートは離れた位置の要素を比べるのでキャッシュの効率が悪く、安定でもありません。

  • A. 最悪 O(n log n) ですが、配列で行うには n に比例する作業用の領域が必要です。
  • B. 正しい。最悪でも O(n log n) で、配列の中だけで並べ替えられます。
  • C. 平均は O(n log n) ですが、最悪の場合は O(n²) になります。
この分野を解く 分野ページへ

関連する計算ツール

ソートの動きを見るツールバブル・選択・挿入・シェル・マージ・クイック・ヒープの7種類のソートを棒グラフで1手ずつ再生。比較と書き込みの回数も比べられる二分探索木・ヒープの可視化ツール値を順に挿入した二分探索木やヒープを図にし、先行順・中間順・後行順のなぞり順、探索の経路、ヒープの配列を表示

データ構造とアルゴリズムの参考書を探す PR

Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。

データ構造とアルゴリズムのほかの問題

  1. (名前, 点数) のデータ (A, 80)、(B, 70)、(C, 80)、(D, 70) がこの順に並んでいる。点数の昇順に安定ソートで並べ替えたときの名前の順はどれか。
  2. クイックソートの計算量が O(n²) になる典型的な場合はどれか。
  3. マージソートで、昇順に整列済みの2つの列 1, 4, 7, 9 と 2, 3, 8, 10 を、先頭どうしを比べて小さい方を出力することを繰り返して1つの列にまとめる(マージする)。片方の列が空になったら、残りは比べずにそのまま出力する。比較の回数は何回か。
  4. 二分ヒープを、根を a[0] とする配列 a[0], a[1], a[2], … に、上の段から順に左から詰めて格納する。a[4] の子と親はどれか。
  5. 親の値が子の値以上になる最大ヒープを、根を a[0] とする配列で表している。ヒープ 50, 30, 40, 10, 20, 35 に45を追加する。末尾に置いてから、親より大きい間は親と交換する操作を行った後の配列はどれか。