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

答えは c です。

クイックソートは「基準を1つ決めて、それより小さい組と大きい組に分ける」を繰り返してデータを並べる方法。

イメージ：身長を並べる時、最初に「だいたいこのくらいの人」を1人選んで、その人より小さい子は左、大きい子は右に分ける → さらに左右それぞれの中でまた1人選んで分ける…を繰り返すと、最後にきれいに並ぶ感じ。

👉 覚え方：「基準（pivot）で分ける」=クイックソート。「分割統治」と呼ばれる速いやり方の代表です。

ほかの選択肢：a 整列済みに1個ずつ差し込む=挿入ソート／b 最小値を順に取り出す=選択ソート／d 隣同士を比べて入れ替える=バブルソート。

なぜこれが正解か

正解は c。クイックソートは基準値（ピボット）を選び、それ未満のグループと以上のグループに分割し、各グループに対して同じ操作を再帰的に適用する分割統治法のアルゴリズム。平均計算量はO(n log n)で、内部ソートの中では最速クラス。

各選択肢の解説

• a「整列済み列の正しい位置に追加」：挿入ソート（insertion sort）。平均O(n²)。
• b「最小値を求め、それを除いて繰り返す」：選択ソート（selection sort）。常にO(n²)。
• d「隣り合うデータを比較し入れ替える」：バブルソート（bubble sort）。平均O(n²)。

覚え方・ひっかけ注意

4大ソートを「クイック=分割」「マージ=合体」「挿入=差し込む」「選択=最小選ぶ」と動詞で紐付けると整理しやすい。クイックは最悪計算量がO(n²)になる点（ピボット選択が偏った場合）にも注意。

理論的背景

クイックソートはホーア（C.A.R. Hoare, 1960年）が考案。基本処理は (1) ピボット選択、(2) パーティション（分割）、(3) 左右部分への再帰、の3ステップ。平均O(n log n)・最悪O(n²)・空間計算量O(log n)（再帰スタック分）。最悪ケースはすでに整列済みデータに対し端点をピボットに選ぶケースで、これを避けるためにランダムピボット、中央値の3点選択（median-of-three）、Introsort（深さ閾値超でヒープソート切替：C++標準ライブラリ採用）が実用される。

実務での使われ方

C言語標準ライブラリ qsort、Pythonのsorted/list.sort（実体はTimsort：マージソート+挿入ソートのハイブリッド）、Javaの Arrays.sort（プリミティブ型はDual-Pivot Quicksort）などソート関数の主力。データベースのORDER BY、外部ソート（メモリに乗らないデータ）ではマージソートが主流。

試験での位置づけ

FEでは「方式を選ぶ」「計算量を答える」「最良/最悪ケースを判定する」が頻出パターン。応用情報・基本情報の午後では擬似コードを読んでpartition関数の動作を追わせる出題、ピボット選択戦略の効率比較が問われる。

選択肢の発展補足

安定ソートか否かも重要：クイックソートは非安定（同値要素の元の順序が保持されない）。安定ソートはマージソート・挿入ソート・バブルソート・基数ソート。FE午後対策では「安定/非安定」「内部/外部」「比較/非比較（基数・バケット）」の3軸で分類して覚えると応用が利く。