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

答えは a「基準を1つ選び、大きい組と小さい組に分けて整列する」です。

クイックソートはトランプを並べるときの賢いやり方。

「真ん中の1枚（基準）」を選んで、それより大きいカードと小さいカードに分けます。それぞれの山でまた同じことを繰り返すと、最終的に全部きれいに並ぶ！

👉 覚え方：「クイック＝速い」「基準で分けて分けて速く整列」。

ほかの選択肢：b 最小を順に取り出す＝選択ソート／c 順番を保ちながら挿入＝挿入ソート／d 隣同士比較＝バブルソート。

なぜこれが正解か

正解は a。クイックソート（Quick Sort）は「分割統治法（Divide and Conquer）」に基づく整列アルゴリズム。手順：(1) 基準要素（ピボット）を1つ選ぶ、(2) ピボットより小さい要素群と大きい要素群に分割、(3) それぞれの部分集合に対して再帰的に同手順を適用、(4) 全体として整列が完成。

各選択肢の解説

• b 誤り：最小要素を順次取り出すのは「選択ソート（Selection Sort）」。計算量はO(n²)。
• c 誤り：要素を順次取り出して既整列部に挿入するのは「挿入ソート（Insertion Sort）」。計算量はO(n²)。
• d 誤り：隣り合う要素を比較・交換するのは「バブルソート（Bubble Sort）」。計算量はO(n²)。

覚え方・ひっかけ注意

4大基本ソートを動作で区別：クイック＝基準で分割／選択＝最小を選ぶ／挿入＝差し込む／バブル＝隣同士交換。クイックソートの平均計算量はO(n log n)で実用上最速級。最悪はO(n²)（既整列で不適切なピボット選択時）。

理論的背景

クイックソート（C.A.R. Hoare, 1960年考案）は分割統治法の代表例で、平均計算量 O(n log n)、最悪 O(n²)、空間計算量 O(log n)（再帰スタック）。安定ソートではない（同値要素の順序が保たれない）。ピボット選択戦略により性能が大きく変わり、「先頭固定」では既整列入力で最悪化、「ランダム選択」「中央値の3つ選択法（Median-of-Three）」で実用性能を改善する。

実務での使われ方

C標準ライブラリの `qsort()`、C++ STL `std::sort`、Java `Arrays.sort()`（プリミティブ型）の内部実装に採用されている。実装上は「Introsort（Introspective Sort）」というハイブリッド方式が主流で、再帰深さが閾値超えたらヒープソートに切替、小規模配列は挿入ソートに切替えて最悪計算量をO(n log n)に保証する。

試験での位置づけ

アルゴリズム分野の最頻出論点。基本情報の科目B（アルゴリズム）でも出題され、4大ソートの計算量・動作の理解は必須。応用情報ではマージソート・ヒープソートとの比較、安定ソートの判別、計算量の証明（再帰木による）が出題される。

選択肢の発展補足

• バブルソート（d）の改良版「シェーカーソート（双方向バブル）」も別問で出題。
• 選択ソート（b）はメモリ書き換え回数が最小（O(n)）でフラッシュメモリ等で有利。
• 挿入ソート（c）は小規模・ほぼ整列済み配列で最速。
• マージソート：常にO(n log n)・安定・追加メモリO(n)必要。
• ヒープソート：常にO(n log n)・不安定・追加メモリO(1)。アルゴリズムの選定では安定性・メモリ・初期状態を考慮する。