はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー!

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

はじめに

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

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

f:id:hanaaaaaachiru:20200303180934g:plain

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

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

その一例がこんな感じ。

  1. ピボットとして一つ選びそれをPとする
  2. 左から順に値を調べ、P以上のものを見つけたらその位置をiとする
  3. 右から順に値を調べ、P以下のものを見つけたらその位置をjとする
  4. iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3での探索はjの一つ左から行う
  5. 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;
    }
}

さいごに

あまりアルゴリズム系は得意ではないので、どのソートがどうだとかはよくわかっていないです。

ただクイックソートは名前からしても早いので、とりあえずソートしたければこれを使えばよい?みたいな感じなのでしょうか。

またWikipediaのソートの箇所にすごくわかりやすく比較が乗っていたのでそちらを参照してみると面白いかもしれません。
ja.wikipedia.org

ではまた。