クイックソート

　クイックソートは、分割統治法の一種であり、適当な基準値（ピボット）に対する大小関係に従って、値集合の分割を繰り返することによってソーティングを実現します。
　1960年に Sir Charles Antony Richard Hoare が開発し、おそらく最も広く用いられるソートアルゴリズムであると思われます。

考え方

配列に用いられている値からピボットを選び、「ピボット未満」と「ピボット以上」に振り分けます。

それぞれの配列に対して、ピボットの選択および配列の分割を繰り返していきます

アルゴリズム

ピボットは、配列の要素から選びます。いま、array[9]の14をピボットしました。
array[9]を分割点と想定して、array[9]より左側に14未満の数を、右側に14以上の数を集めていくことを計画します。

分割

左端 array[0] から右端に向かって、また、右端 array[19] から左端に向かって配列を走査します。このとき条件に合致しない、すなわち

条件に合致しない値の組について、array[1]とarray[19]の位置関係は降順であるとき、互いの位置を交換します。

これを、左からの操作を右端に向かって、右からの走査を左端に向かって繰り返していきます。

　次は、左側からの走査において、ピボット以上の値として「ピボット自身」を見つけた状態です。

このようなことはしばしば起こりますが、そのまま交換します。

走査を続けます。左側からの走査で array[11]に14 以上の数が見つかり、右側からの捜査で array[14]に14 以下の数が見つかりました。このまま交換します。なお、array[16]の値 14 は、ピボットとして、分割点と想定していたarray[9]の要素でした。

さらに走査を続けて、左側からの走査で array[14]に14 以上の数が見つかり、右側からの捜査で array[13]に14 以下の数が見つかりました。

array	pivot未満を集める←	pivot	→pivot以上を集める
[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]	[12]	[13]	[14]	[15]	[16]	[17]	[18]	[19]
10	15	6	13	12	16	18	9	4	14	1	17	0	11	8	19	5	3	7	2

このとき、array[13]とarray[14]は、昇順に並んでいるので交換を行わず、この時点で走査を終了します。
ピボット以上の要素とピボット以下の要素が同じ要素番号であった場合（配列要素が2個の場合に必ず起こります）も、その時点で走査を終了します。

分割点は、左側からの走査において、最後に見つかったarray[14] が相応であることが分かります。

配列の分割が終わったら、分割点[14]を境に、array[0]～[13] と array[14]～[19] のそれぞれに対して分割を繰り返します。

分割の終了、順序の確定

ピボットの与え方

　先述の分割の方法では、ピボットが最小値の場合、「要素数0の配列」と「分割前の配列そのもの」に分かれてしまい、無駄な処理となります。ひいては、ピボットとして（偶発的に）最小値を取り続けると、無限ループになります。

　配列の分割の仕方から想像できますが、ピボットとして理想の値は中央値です。しかしながら、中央値はソートを介して得られるため、中央値にこだわることは賢明ではありません。通常は次の方法のいずれかを採ります。

　当初のピボットの位置は、あくまで「分割点の想定」に過ぎません。結局のところ「ピボットの値は、配列要素の範囲内にあれば良く、必ずしも配列要素から選ばなければならないということではない」ことも分かります。

プログラムソース

　クイックソートは、分割した配列のそれぞれに対して分割を繰り返すため、容易な実装のために再帰的な関数として定義する例が多く見られます。

	array1	array2
array	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]	[12]	[13]	[14]	[15]	[16]	[17]	[18]	[19]
10	2	6	13	12	7	3	9	4	5	1	8	0	11	17	19	14	18	16	15

　倍精度実数配列に対するソースを示します。ここで、配列の要素数は、配列の定義等によって既知であるとします。
　数値配列に対する汎用性を考慮しており、このまま使用する場合は、引数にあたる配列のデータ型をキャストしてください。

再起呼出しを用いる例

void quicksort(double array, int first, int last)
{
    int       i, j;           /*配列を走査するためのカウンタ*/
    double    pivot, temp;    /*ピボット および 値交換用の変数*/

    pivot = array[(first + last) / 2];    /*配列の中央の要素をピボットとする例*/
    
    i = first;  j = last;

    while (1)
    {
        while(array[i] <= pivot) i++;    /*左側からの走査でピボット以上の値を探す*/
        while(array[j] >= pivot) j--;    /*右側からの走査でピボット以下の値を探す*/

        /*array[i]（ピボット以上） と array[j]（ピボット以下）が昇順に並んでいるかを要素番号から判断*/
        if (i >= j)    break;    /*昇順であれば走査を終了する*/
        
        /*配列要素の交換*/
        tmp = array[i];  array[i] = array[j];  array[j] = temp;
            /*array[i] = array[j]でも交換を行うことに注意*/
            /*array[i] と array[j]の大小関係を判断することが余分な演算（比較）となるため*/
        
        i++;  j--;    /*左側、右側共に次の要素に移動*/
    }
    
    /*再帰呼び出し…分割点はarray[i]*/
    if (first < i - 1)   quicksort(array, first , i - 1);
    if (j + 1 < last)    quicksort(array, i, last);
}

再起呼出しを用いない例

　配列を分割する手続きは、再帰呼び出しの場合と同様です。分割点がarray[i]に定まるとき、配列は

に分かれ、それぞれに対して分割を繰り返すことになります。2つの配列を同時に処理することはできないので、一方の配列の情報を保管しておきます。情報の保管にはスタックを用い、ソートを行う配列の要素番号の最初と最後をそれぞれスタックに積みます。
　優先的に処理するのは分割後のサイズが小さい配列です。サイズが大きな配列はそれだけ多く分割を繰り返すことになり、余分にスタックを消費してしまうためです。最も多くスタックを利用するケースは、2分割されたそれぞれの配列の長さが常に等しい状態であり、これは、（偶発的に）ピボットが常に中央値に設定された場合であると言えます。

　THRESHOLD は、ソートを行う配列の要素数に対する閾値であり、要素数が THRESHOLD 未満の場合は挿入ソートへの切替えを行っています。
　以上より、スタックのサイズ（STSIZE で定義しています）は、分割が最も多く行われるときの分割の回数として考えられ、最初の配列要素数 n に対して以下の式を満たす STSIZE として求められます。

具体的に、100万件のデータをクイックソートだけで行う場合（THRESHOLD = 1）、スタックサイズは STSIZE > log₂1000000 ≒ 13.8 であり、14 以上あれば充分であることが分かります。

#define THRESHOLD 10  /* クイックソートから挿入ソートに切り替えるための、配列の要素数 */
#define STSIZE 32  /* スタックサイズ */

void quicksort(double array, int n)
{
    int        i, j;                /*配列を走査するためのカウンタ*/
    int        first, last, sp;     /*配列の始点と終点*/
    int        st_first[STSIZE],    /*対象となる配列の始点を格納するためのリスト（スタック）*/
               st_last[STSIZE];     /*対象となる配列の終点を格納するためのリスト（スタック）*/
    int        sp;                  /*スタックポインタ*/
    double     pivot, temp;         /*ピボット および 値交換用の変数*/

    /*初期状態…始点: 要素番号[0]、終点: 要素番号[n-1]、分割点…未定のため便宜上要素番号[0]*/
    first = 0;  last = n - 1;  sp = 0; 

    while(1)
    {
        /*ソートを行う配列の要素数が、挿入ソートに切替える条件となる要素数以下の場合*/
        if (last - first <= THRESHOLD)
        {
            if (sp == 0) break;    /*スタックが空であれば、ループを抜けてinssort() （挿入ソート）に切替える*/

            /*次にクイックソートを行う配列の範囲を決めるため、始点と終点の要素番号をスタックから取り出す*/
            sp--;
            first = st_first[sp];
            last = st_last[sp];
        }
        
        pivot = array[(first + last) / 2];    /*配列の中央の要素をピボットとする例*/

        i = first;  j = last;

        /*配列の分割…再帰呼び出しのクイックソートと同様*/
        while(1)
        {
            while (array[i] < pivot) i++;
            while (pivot < array[j]) j--;

            if (i >= j) break;
            temp = array[i];  array[i] = array[j];  array[j] = temp;
            i++;  j--;
        }
        /*ここまで*/
        
        /*この時点で、分割点はarray[i]であり、*/
        /*配列はarray[first]～array[i-1]（左側）とarray[i]～array[last]（右側）に分割される*/
        
        /*array[first]～array[i-1]のサイズとarray[i]～array[last]のサイズを比較*/
        /*array[first]～array[i-1]のサイズが大きい*/
        if (i - first > last - j)
        {
            /*クイックソート続行のための条件*/
            /*ソートを行う配列の要素数が、挿入ソートに切替える条件となる要素数より大きい場合*/
            if (i - first > THRESHOLD)
            {
                /*現在のスタック位置に、配列の情報を記録*/
                st_first[sp] = first;    /*始点を記録*/
                st_last[sp] = i - 1;    /*終点を記録*/
                sp++;    /*スタックポインタをインクリメント*/
            }
            first = i;   /*サイズの小さい右側の配列の始点を、次にソートを行う配列の始点としてセット、終点はそのまま*/
        }
        
        /*array[i]～array[last]のサイズが大きい*/
        else
        {
            /*クイックソート続行のための条件*/
            if (last - j > THRESHOLD)
            {
                /*現在のスタック位置に、配列の情報を記録*/
                st_first[sp] = i + 1;
                st_last[sp] = last;
                sp++;
            }
            last = i - 1;   /*サイズの大きい左側の配列の終点を、次にソートを行う配列の終点としてセット、始点はそのまま*/
        }
    }
    
    inssort(array, n);        /*挿入ソートに切替える*/
}