ソート

チェックポイント

• バブルソート Basis バブルソート（bubble sort）はスワップが不要になるまで配列を繰り返し走査し、隣接する逆順ペアを交換する。このチェックポイントでは、アルゴリズムの導出、正しさの証明、$O(n^2)$ の最悪ケースが実用より教育目的に留まる理由を解説する。
• バケットソート Basis バケットソート（bucket sort）はキー関数に基づいて要素を固定数のバケットに分配し、各バケットをソートして結果を結合する。このチェックポイントでは、アルゴリズムの導出、期待 $O(n)$ 実行時間が入力分布にどう依存するか、カウントソートとの対比を解説する。
• カウントソート Basis カウントソート（counting sort）は要素を比較する代わりに出現回数を数えることで、既知の小さな範囲の整数を $O(n+k)$ 時間でソートする。このチェックポイントでは、アルゴリズムの導出、比較ベースのソートとの対比、線形実行時間がキー範囲 $k$ のサイズに決定的に依存する理由を解説する。
• 挿入ソート Basis 挿入ソート（insertion sort）は各新しい要素を正しい位置に達するまで左にシフトすることでソート済み前半部分を 1 要素ずつ構築する。このチェックポイントでは、アルゴリズムの導出、ループ不変条件による正しさの証明、$O(n^2)$ の最悪ケースとほぼソート済みデータに対する $O(n)$ の最良ケースを解説する。
• マージソート Basis マージソート（merge sort）は配列を半分に分割し、各半分を再帰的にソートして 2 つのソート済み半分を結合することで、あらゆるケースで $O(n \\log n)$ 時間を達成する。このチェックポイントでは Zig でアルゴリズムを実装し、ループ不変条件による正しさの証明を行い、分割統治の構造が二乗ソートより良い最悪ケースを保証する理由を解説する。
• クイックソート Basis クイックソート（quick sort）はピボット要素を選び、それより小さいものを左に、大きいものを右に配置するよう配列を分割し、各側を再帰的にソートすることで $O(n \\log n)$ の期待時間を達成する。このチェックポイントでは分割ステップの導出、平均と最悪の計算量の解析、ピボットの選択が性能に与える影響を解説する。
• 基数ソート Basis 基数ソート（radix sort）は最下位桁から最上位桁へと整数を桁ごとにソートし、各パスで安定なサブルーチン（カウントソートなど）を使うことで桁数を $k$ として $O(nk)$ 時間を達成する。このチェックポイントでは、アルゴリズムの導出、内側のソートの安定性がなぜ不可欠かの証明、基数ソートが比較ベースの $O(n \\log n)$ アルゴリズムを上回る場面の分析を行う。
• 選択ソート Basis 選択ソート（selection sort）は未ソートの後半部分の最小値を繰り返し見つけてその位置にスワップすることで配列をソートする。このチェックポイントでは、アルゴリズムの導出、ソート済み配列が得られることの証明、そして入力に関わらず常に $\\Theta(n^2)$ 回の比較を行う理由を分析する。