クイックソートとは

クイックソート とはその名の通り、非常に高速なソートアルゴリズムです。数あるソートアルゴリズムの中で実用上最速と言われています。ただし当然ですが、すべての条件で最速という訳ではありません。

任意のピボット(基準値)をデータの中から選び、ピボットより小さい値をデータの前半に、ピボットより大きい値を後半に移動(分割)させます。前半と後半それぞれで再帰的呼び出しによりソートします。分割統治法と呼ばれる手法です。

クイックソートは 不安定 な 内部 ソートです。平均計算量は O(n log n) です。ただし、最悪計算量が O(n2) なので、これに陥らないようにピボットを選ぶ必要があります。

クイックソートのシミュレーション

背景色が黄色のタイミングでピボットの値との比較が実行されています。緑色のデータが現在分割中のデータです。赤字のデータが現在のピボットです。分割を行うデータの両端から、ピボットより大きいと小さい値を見つけて交換しています。あとは再帰的に前半と後半の領域で繰り返しクイックソートが実行されていきます。

アルゴリズムの解説

  1. データの中からピボット(基準値)を選びます。
  2. 対象のデータの左端からピボットより小さい値を探します。
  3. 対象のデータの右端からピボットより大きい値を探します。
  4. 見つかった値同士を交換します。
  5. 2～4 を繰り返し、ピボットより小さい値を左側に、大きい値を右側に集めます。
  6. 左側と右側の領域をそれぞれ再帰的に上記の処理を繰り返します。

ピボットの選び方

ピボットの選び方を工夫することで、最悪計算量 O(n2) に陥る可能性を抑えられます。データの中から適当な3値を選び、その中央値を選ぶのが良いとされています。

サンプルコード

C#

public static void QuickSort<T>(T[] array, int left, int right) where T : IComparable<T>
{
    if (left < right)
    {
        // ピボット決定（配列の先頭、真ん中、末尾の3つの値の中央値とする）
        T pivot = Median(array[left], array[(left + (right - left) / 2)], array[right]);

        int l = left;
        int r = right;

        // ピボットを中心に、分ける
        while (true)
        {
            // ピボットより小さいデータのインデックスを見つける
            while (array[l].CompareTo(pivot) < 0) l++;
            // ピボットより大きいデータのインデックスを見つける
            while (array[r].CompareTo(pivot) > 0) r--;
            // 見つかったインデックスの大小が逆転していれば、終了
            if (l >= r) break;

            // 見つかった要素を交換
            Swap(ref array[l], ref array[r]);

            l++; r--;
        }
        // 左右に分けた配列を再帰的にソート
        QuickSort(array, left, l - 1);
        QuickSort(array, r + 1, right);
    }
}

// 3値の中から中央値を返す
public static T Median<T>(T x, T y, T z) where T : IComparable<T>
{
    if (x.CompareTo(y) < 0)
    {
        return x.CompareTo(z) < 0 ? (y.CompareTo(z) < 0 ? y : z) : x;
    }
    else
    {
        return y.CompareTo(z) < 0 ? (x.CompareTo(z) < 0 ? x : z) : y;
    }
}

public static void Swap<T>(ref T a, ref T b)
{
    var tmp = a;
    a = b;
    b = tmp;
}