Zenn
📘

【C#アルゴリズム】効率的なソートアルゴリズム

2024/11/22に公開
C#
アルゴリズム
sort
tech

はじめに

paiza　、アルゴリズムの本で効率的なソートアルゴリズムについて学んだのでまとめました。

素朴なソートアルゴリズムはこちらにまとめています。具体的には挿入ソート、選択ソート、バブルソートについてまとめています。

1. シェルソート (Shell Sort)

概要:
挿入ソートを改良したアルゴリズムで、間隔（ギャップ）hを利用して遠く離れた要素を比較・交換し、段階的にギャップhを小さくしながらソートします。

  • 時間計算量: 平均 O(n^{1.25}), 最悪 O(n^{2})
  • 特徴: 挿入ソートより効率的

コード:

// シェルソートの実装
private static void ShellSort(int[] A, int n, int[] h)
{
    // ギャップシーケンス h に基づいて、各ギャップで挿入ソートを実行
    foreach (var hi in h)
    {
        InsertionSort(A, n, hi);
    }
}

// ギャップ指定型挿入ソート
private static void InsertionSort(int[] A, int n, int hi)
{
    // hi だけ離れた要素間で挿入ソートを実行
    for (int i = hi; i < n; i++)
    {
        // 現在の要素を一時的に保存
        int x = A[i];
        int j = i - hi;

        // ギャップごとの要素を後方にシフト
        while (j >= 0 && A[j] > x)
        {
            A[j + hi] = A[j];
            j -= hi;
        }
        
        // 一時保存していた値を正しい位置に配置
        A[j + hi] = x;
    }
}

2. マージソート (Merge Sort)

概要:
データ列を二分し、それぞれをマージソートした後それらを「マージ (統合) 」することを繰り返すソートアルゴリズムです。

  • 時間計算量: 常に O(n \log n)
  • 特徴: 安定ソート、大量データに強い

コード:

// マージソートの実装
private static void MergeSort(int[] A, int left, int right)
{
    // ベースケース: 部分配列の要素数が1以下なら終了
    if (left + 1 < right)
    {
        // 配列を中央で分割
        int mid = (left + right) / 2;

        // 左側部分配列を再帰的にソート
        MergeSort(A, left, mid);

        // 右側部分配列を再帰的にソート
        MergeSort(A, mid, right);

        // 左右の部分配列をマージ
        Merge(A, left, mid, right);
    }
}

// 2つのソート済み部分配列をマージする補助メソッド
private static void Merge(int[] A, int left, int mid, int right)
{
    // 左部分配列の長さと右部分配列の長さを計算
    int nl = mid - left;
    int nr = right - mid;

    // 左部分配列用の一時配列を作成し、データをコピー
    int[] L = new int[nl + 1];
    for (int i = 0; i < nl; i++)
    {
        L[i] = A[left + i];
    }

    // 右部分配列用の一時配列を作成し、データをコピー
    int[] R = new int[nr + 1];
    for (int i = 0; i < nr; i++)
    {
        R[i] = A[mid + i];
    }

    // 番兵として `int.MaxValue` を設定 (無限大として扱う)
    L[nl] = int.MaxValue;
    R[nr] = int.MaxValue;

    // 左右の配列をマージするためのインデックス
    int lindex = 0;
    int rindex = 0;

    // 元の配列にマージ結果を書き戻す
    for (int i = left; i < right; i++)
    {
        // 左部分配列の要素が右部分配列より小さい場合
        if (L[lindex] < R[rindex])
        {
            A[i] = L[lindex]; // 左側の値を選択
            lindex++;         // 左配列の次の要素に進む
        }
        else
        {
            A[i] = R[rindex]; // 右側の値を選択
            rindex++;         // 右配列の次の要素に進む
        }
    }
}

3. クイックソート (Quick Sort)

概要:
基準値（ピボット）を選び、それより小さい要素と大きい要素に分けて再帰的にソートします。ピポットの選び方は複数ありますが、例ではpaizaと同様に分割したうちの一番後ろの要素をピボットとしています。

  • 時間計算量: 平均 O(n \log n), 最悪 O(n^2)
  • 特徴: 高速、実装がシンプル（効率を上げるにはピボットの選び方が重要）

コード:

// クイックソートの実装
public static void QuickSort(int[] A, int left, int right)
{
    // ベースケース: 部分配列の要素数が 1 以下なら処理を終了
    if (left + 1 >= right) return;

    // ピボットの選択: 配列の右端の値をピボットとする
    int pivod = A[right - 1];

    // ピボットより小さい値を左側に集めるためのインデックス
    int curIndex = left;

    // ピボットより小さい値を左側に移動
    for (int i = left; i < right - 1; i++)
    {
        // 現在の値がピボット未満であれば、左側にスワップ
        if (A[i] < pivod)
        {
            Swap(A, curIndex, i);
            curIndex++;
        }
    }

    // 最後にピボットを適切な位置に移動
    Swap(A, curIndex, right - 1);

    // 再帰的に左部分配列をソート
    QuickSort(A, left, curIndex);

    // 再帰的に右部分配列をソート
    QuickSort(A, curIndex + 1, right);
}

// 配列内の2つの要素をスワップするヘルパーメソッド
private static void Swap(int[] A, int x, int y)
{
    int temp = A[y];
    A[y] = A[x];
    A[x] = temp;
}

4. ヒープソート (Heap Sort)

概要:
配列をヒープ構造（完全二分木）に変換し、最大値または最小値を効率的に取り出します。

  • 時間計算量: 平均・最悪 O(n \log n)
  • 特徴: すべてのソートではなく下からk個取り出すという場合には、O(s + k \log n)で済み、有効

5. バケットソート (Bucket Sort)

概要:
データを範囲ごとにバケットに分割し、それぞれを個別にソートして結合します。要素の取りうる範囲が有限個に限られている場合にのみ使える方法です。

  • 時間計算量: バケットの挿入にO(n)、バケットの接続にバケット数mとするとO(M)かかります。
  • 特徴: 数要素の取りうる範囲が有限個に限られている場合にのみ使える

6. 基数ソート (Radix Sort)

概要:
バケットソートの改良版。数値の桁ごとにソート（0～9）を繰り返します。日付など、有限の数値が段階的に並んでいるものであれば何にでも適用可能です。

  • 時間計算量: 桁数をk、バケット数をmとすると、O(k(n + m))
  • 特徴: 大量の数値ではバケットソートよりも効率的

まとめ

アルゴリズム名 平均時間計算量 最悪時間計算量 特徴
シェルソート O(n^{1.25}) O(n^2) 挿入ソートの改良版。間隔を調整しながらソート。
マージソート O(n \log n) O(n \log n) 分割統治法を使用。大量データ向き。
クイックソート O(n \log n) O(n^2) ピボットを選んで分割統治法を使用。高速だが最悪ケースに注意。
ヒープソート O(n \log n) O(n \log n) 下からk個取り出すという場合には有効。
バケットソート O(n + m) O(n + m) 数要素の取りうる範囲が有限個に限られている場合にのみ使える
基数ソート O(k(n + m)) O(k(n + m)) 大量の数値ではバケットソートよりも効率的

結局どれが早いのか

結局早いのはクイックソートだと考えられているようです。
参考までに、クイックソートを可視化した映像をつけておきます。
https://www.youtube.com/watch?v=kPRA0W1kECg

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
https://amzn.to/3YtOnpz

Discussion