概要
#

昇順の場合

基準となる値（ピボット）を決める。

基準値より小さいものを基準値の前方に、大きいものを後方へ移動

基準値の前方、後方それぞれで同じことを繰り返す。

分割統治方の一種（重要）。

そのうち動的計画法と合わせて解説する日が来るかも。。。

新たに配列を生成しないタイプの内部ソート。

安定ではない。

計算時間
#

O(nlogn)

自分的イメージ；マージソートと同じく徐々に範囲を狭めながら再帰的に繰り返すので階層はlogn段階。各段階において合計だいたいn回くらいの比較を行うのでnlogn。

自分的にはすごく納得いく考え方なんだけど大体だし図とかないとわかりづらいので参考程度で。そのうち図とかつけたいですね。

最悪時はO(n^2)

式的にはマージソートと同じ平均計算量だが基本的にマージソートより早い。

しかし最悪時がものすごく遅い。（ソート済みの配列で常に左端をピボットとして指定した時など）

ただ、ピボットの選び方を工夫することでたいてい避けられる。

実装
#

実装してみた。

言語はC#。再帰的。

実際に前回のマージソートやシェルソートと比較してみましたがちゃんと早かったです。

再帰を使った実装は簡潔ですが、Nが大きくなるとスタック領域が足りなくなることがあるので注意が必要です。

複雑になったとしても再帰を使わないほうがメモリには優しいんですって。

using System.Collections;
using System.Collections.Generic;
using System;

public class QuickSort:ISort
{
    /// <summary>
    ///基本的な手順は以下の通りである。
    ///基準(Pivot)を決める
    ///基準より左に基準以下を。右に以上を。
    ///左、右でそれぞれ再起的に繰り返す
    ///計算量O(nlogn)
    ///最悪を避ければMergeより早い
    /// </summary>
    public int[] Sort(int[] target)
    {
        return QuickSortRecursive(target,0,target.Length - 1);
    }

    int[] QuickSortRecursive(int[] target,int startIndex,int endIndex)
    {
        if(endIndex - startIndex<=0){
        //if(endIndex - startIndex<=1)にしたせいでハマった…
            return target;
        }

        //分割する
        int pivot = GetPivot(target,startIndex,endIndex);

        int l = startIndex;
        int r = endIndex;

        while(true){

            //pivotより大きいのを見つけるまで左のindexを進める
            while(target[l] < pivot && l <= endIndex){
                l ++; 
            }
            //pivotより小さいのを見つけるまで右のindexを進める
            while(target[r] > pivot && r >= startIndex){
                r --; 
            }

            if(l >= r){
                break;
            }

            int tmp = target [r];
            target[r] = target[l];
            target[l] = tmp;
        }

        //左
        QuickSortRecursive(target,startIndex,r - 1);
        //右
        QuickSortRecursive(target,r + 1,endIndex);

        return target;
    }

    static int GetHalf(int left,int right)
    {
        return left + (right - left)/2;
    }

    /// <summary>
    /// 三つ取ってその中で真ん中の値を返す
    /// </summary>
    static int GetPivot(int[] target,int left,int right)
    {
        int half = GetHalf(left,right);
        int min = Math.Min(target[left],target[right]);
        int max = Math.Max(target[left],target[right]);
        if(target[half] < min ){
            return min;
        }
        if(target[half] > max){
            return max;
        }
        return target[half];
    }
}

//N=10000で回してみた結果
-------ShellSort------
time : 00:00:00.0724777
ミリ秒 : 72
-------------------------
-------MergeSort------
time : 00:00:00.0056750
ミリ秒 : 5
-------------------------
-------QuickSort------
time : 00:00:00.0030104
ミリ秒 : 3
-------------------------

今まで自分でコード書いててWhileループってそんなに使わなかったんですがアルゴリズム系のコードを調べると結構使っててへ〜って思いました。ちゃんと使うと便利ですね。というかfor文でやろうとしたら全然できなかったです。

使い分けていこうと思いました。

終わりです。

ではまた。