基本情報 平成30年度 春期 問6：テクノロジ系に関する問題

答えは c です。

クイックソート＝「基準値（ピボット）」を1つ決めて、それより小さいグループと大きいグループに2分割→さらに各グループの中で同じことを繰り返すソート。

例：[5,3,8,1,4]→基準4にすると→[3,1] [5,8] →各グループでまた基準を選ぶ…と繰り返して並び替えます。

👉 覚え方：クイック＝基準で半分に分けて、また半分！

ほかの選択肢：a 整列済みに挿入＝挿入ソート／b 最小値を順に選ぶ＝選択ソート／d 隣を入れ替え＝バブルソート。

なぜこれが正解か

正解は c。クイックソート（Quicksort）は、データから基準値（ピボット）を選び、ピボットより小さい値の集合と大きい値の集合に分割（パーティション）し、各部分集合に対して再帰的に同じ操作を繰り返すソート。Tony Hoare が1961年に発明、平均計算量 O(n log n)、最悪 O(n²) の代表的な分割統治アルゴリズム。

各選択肢の解説

• a 整列済みに新要素を挿入：挿入ソート（Insertion Sort）、O(n²)。
• b 最小値を順次選ぶ：選択ソート（Selection Sort）、O(n²)。
• c 基準値で分割→再帰：クイックソート → 正解。
• d 隣接交換で端へ移動：バブルソート（Bubble Sort）、O(n²)。

覚え方・ひっかけ注意

主要ソートの計算量を暗記：

• O(n²)：バブル、選択、挿入。
• O(n log n)：クイック（平均）、マージ、ヒープ。
• O(n)：基数ソート、計数ソート（前提条件あり）。

クイックソートは実装によって安定性が変わる点、最悪O(n²)の落とし穴があり実用上はピボット選択を工夫（中央値法、ランダム化）する。

アルゴリズム詳細

クイックソートの再帰関係：T(n) = T(k) + T(n-1-k) + O(n)（kはピボット未満の要素数）。

• 最良/平均：ピボットが中央値付近 → T(n) ≈ 2T(n/2) + O(n) = O(n log n)
• 最悪：ピボットが端の値（ソート済み配列＋単純な「先頭」ピボット選択時） → T(n) = T(n-1) + O(n) = O(n²)
• 空間計算量：再帰呼出のスタック分 O(log n) 平均、O(n) 最悪。

ピボット選択戦略

• 先頭/末尾要素：シンプルだが整列済みデータに弱い。
• ランダム選択：期待計算量 O(n log n) を確率的に保証。
• 中央値法（median-of-three）：先頭・中央・末尾の中央値をピボット採用。実用的解。
• introsort：再帰深度が log n を超えたらヒープソートにフォールバック（C++ std::sort、Rust等で採用）。
• dual-pivot quicksort：2つのピボットで3分割（Java 7以降の Arrays.sort で採用）。

安定性

クイックソートは不安定（同じキーの相対順序が保たれない）。安定性が必要ならマージソート（追加メモリO(n)）、または間接ソート（タプルで元のインデックス保持）を採用。

主要ソートアルゴリズム比較

| ソート | 最良 | 平均 | 最悪 | 空間 | 安定 |

|---|---|---|---|---|---|

| バブル | O(n) | O(n²) | O(n²) | O(1) | 安定 |

| 挿入 | O(n) | O(n²) | O(n²) | O(1) | 安定 |

| 選択 | O(n²) | O(n²) | O(n²) | O(1) | 不安定 |

| クイック | O(n log n) | O(n log n) | O(n²) | O(log n) | 不安定 |

| マージ | O(n log n) | O(n log n) | O(n log n) | O(n) | 安定 |

| ヒープ | O(n log n) | O(n log n) | O(n log n) | O(1) | 不安定 |

| 基数 | O(d·n) | O(d·n) | O(d·n) | O(n+k) | 安定 |

試験での位置づけ

FE「アルゴリズム」分野で毎期出題の最重要領域。各ソートの説明文判別、計算量、安定性、適用条件の理解は確実な得点源。応用情報・データベーススペシャリストでは外部ソート（メモリに乗らないデータ）、並列ソート、近似ソートまで踏み込む。

実装上の注意点

• 再帰によるスタックオーバーフロー：尾再帰最適化、反復化で対策。
• 小規模配列：n が小さいとき挿入ソートのほうが定数倍高速。実装によってはn<16等で切り替え。
• キャッシュ局所性：マージソートより一般にキャッシュフレンドリ。
• 並列化：分割部分集合を並列処理可能、GPU実装も存在。

選択肢の発展補足

dのバブルソートは最良ケース O(n)（ソート済み判定の早期終了実装）が可能。aの挿入ソートは部分整列データに強い（適応的ソート）。マージソートは外部ソート（巨大データのファイル分割マージ）の基本、応用情報・データベーススペシャリスト頻出。