【C#】クイックソートを実装してみる

はじめに

今回はクイックソートについて取り上げていきたいと思います。

クイックソートは最悪計算時間は𝑂(𝑛^2)ですが、平均計算時間が𝑂(𝑛log𝑛)である比較的高速なソートです。

f:id:hanaaaaaachiru:20200303180934g:plain

実際の処理の流れをWikipediaから引っ張ってきました。

適当な数（ピボット）を選択する（この場合はデータの総数の中央値が望ましい）
ピボットより小さい数を前方、大きい数を後方に移動させる（分割）
二分割された各々のデータを、それぞれソートする

その一例がこんな感じ。

ピボットとして一つ選びそれをPとする
左から順に値を調べ、P以上のものを見つけたらその位置をiとする
右から順に値を調べ、P以下のものを見つけたらその位置をjとする
iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3での探索はjの一つ左から行う
2に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分け、そのそれぞれに対して再帰的に1からの手順を行う。要素数が1以下の領域ができた場合、その領域は確定とする

クイックソート - Wikipedia

コード

QuickSort.cs

using System;

public class Sort
{
    public static void Main(string[] args)
    {
        var targetArray = new int[11] { 11, 300, 10, 51, 126, 1, 53, 14, 12, 55, 6 };

        Console.WriteLine(string.Join(",", targetArray));

        // クイックソートを行う
        QuickSort(targetArray, 0, targetArray.Length - 1);

        Console.WriteLine(string.Join(",", targetArray));
    }

    /// <summary>
    /// クイックソート
    /// </summary>
    /// <param name="array">対象の配列</param>
    /// <param name="left">ソート範囲の最初のインデックス</param>
    /// <param name="right">ソート範囲の最後のインデックス</param>
    public static void QuickSort<T>(T[] array, int left, int right) where T : IComparable<T>
    {
        // 範囲が一つだけなら処理を抜ける
        if (left >= right) return;

        // ピポットを選択(範囲の先頭・真ん中・末尾の中央値を使用)
        T pivot = Median(array[left], array[(left + right) / 2], array[right]);

        int i = left;
        int j = right;

        while (i <= j)
        {
            // array[i] < pivot まで左から探索
            while (i < right && array[i].CompareTo(pivot) < 0) i++;
            // array[i] >= pivot まで右から探索
            while (j > left && array[j].CompareTo(pivot) >= 0) j--;

            if (i > j) break;
            Swap<T>(ref array[i], ref array[j]);

            // 交換を行った要素の次の要素にインデックスを進める
            i++;
            j--;
        }

        QuickSort(array, left, i - 1);
        QuickSort(array, i, right);
    }

    /// <summary>
    /// 中央値を求める
    /// </summary>
    private static T Median<T>(T x, T y, T z) where T : IComparable<T>
    {
        // x > y なら1以上の整数値が返される
        if (x.CompareTo(y) > 0) Swap(ref x, ref y);
        if (x.CompareTo(z) > 0) Swap(ref x, ref z);
        if (y.CompareTo(z) > 0) Swap(ref y, ref z);
        return y;
    }

    /// <summary>
    /// 参照を入れ替える(値型だと変数のコピーになってしまうため)
    /// </summary>
    private static void Swap<T>(ref T x, ref T y) where T : IComparable<T>
    {
        var tmp = x;
        x = y;
        y = tmp;
    }
}