クイックソートとは

**分割統治法（Divide-and-Conquer）**に基づいたアルゴリズムです。

基準値（ピボット）より大きいグループと小さいグループに分割し，分割後の要素数が1になるまで再帰的に分割を繰り返します。

コードだけ見たい方はこちら

計算量

計算量とは，実行時間を入力データ量の関数で表したものです。
O(オーダー)記法が用いられます。

クイックソートの平均計算量は O(n logn) で，最悪計算量は O(n^2) です。

なぜそうなるのかは，計算量についてで簡単に解説しています。

処理の流れ

調べる範囲の両端にポインタ( left と right )をセットし，任意のピボットを決める。
left はピボットより大きい値を指すまで右に進む。right はピボットより小さい値を指すまで左に進む。
二つのポインタが**衝突(※)**すれば，そこで分割終了。5へ。
衝突していなければ，左右のポインタが指している値を交換する。2へ。
分割後の左右それぞれブロックにおいて，要素が二つ以上あれば再帰的に同じ処理をする。

※ 二つのポインタが衝突するとは
(1) [right | left] のように左右が逆になり交差して止まった場合
(2) left と right が同じ要素を指して止まった場合

(1)は二つのポインタの間が分割の境界線となる。
(2)は指してる要素がピボットの場合である。ピボットの位置はそこで確定するので，再帰処理の対象に含める必要はない。

よって，再帰処理の対象範囲は以下になります。

先頭～ left-1
right+1 ～末尾

PHPでの実装

quickSort.php

/**
 * クイックソート
 * 渡された配列を破壊的に変更します
 *
 * @param int $start 調べる範囲の先頭の位置（インデックス番号）
 * @param int $end 調べる範囲の末尾の位置（インデックス番号）
 * @param array $arr ソートしたい配列　参照渡し
 * @return void
 */
function quickSort(int $start, int $end, array &$arr): void
{
    // ソートする必要がない場合
    if($end <= $start || count($arr) < 2 ){
        return;
    }

    // 任意の値（ここでは真ん中の位置にある値）をピボットに設定
    $pivot = $arr[(int)(($start + $end) / 2)];

    // 両端をそれぞれポインタの初期値として設定
    [$left, $right] = [$start, $end];

    // 2つに分割する
    while (true) {
        // $left の値がピボットより小さければ，ポインタを右へ進める
        while ($arr[$left] < $pivot) {
            $left++;
        }
        // $right の値がピボットより大きければ，ポインタを左へ進める
        while ($pivot < $arr[$right]) {
            $right--;
        }
        // $left と $right が衝突したらループを抜ける
        if ($right <= $left){
            break;
        }
        // $left と $right の値をスワップ
        [$arr[$left], $arr[$right]] = [$arr[$right], $arr[$left]];
        // 交換したら1つ進める
        $left++;
        $right--;
    }

    // 左側に2つ以上要素が存在するなら再帰的にソート
    if ($start < $left-1) {
        quickSort($start, $left-1, $arr);
    }
    // 右側に2つ以上要素が存在するなら再帰的にソート
    if ($right+1 < $end) {
        quickSort($right+1, $end, $arr);
    }

}

ソートする

// ソートする
$a = range(0, 100);
shuffle($a);
quickSort(0, count($a)-1, $a);

※ PHPには標準でsort関数が用意されています。これは，C言語レベルでソートを実装しています。わざわざ自分で実装する必要はありません。

蛇足（PHPのソート関数について）

sort()はクイックソートで実装されているみたいです。

PHP の大半のソート関数と同様、sort() は » Quicksort でそれを実装しています。ピボットは、既にソート済みの部分に対して時間的に最適なところを選択します。

PHPのソースです。処理の実体は恐らくここ（php-src/Zend/zend_sort.c）にあります。
要素数が5つ以下の場合は，シンプルなソートをしているようですね。

計算量について

直感的に理解できるように簡単に考えます。

クイックソートは，マージソートと同じく分割統治法です。

データの数を n とします。データを2分割していき，最終的に分割後のデータ数が1になればソートが完了します。

ここで，何回分割を繰り返せば良いでしょうか？

例えば n=8 で考えると，8 → 4 → 2 → 1 のように3回の分割が必要です。
8 × (1/2) × (1/2) × (1/2) = 1 という計算をしています。

× (1/2) を何回行うのかを知りたいのです。

これを一般化すると以下の式になります。k は任意の正の整数です。

n (1/2)^k = 1

これを k について解くと

n (1/2)^k = 1\\
(1/2)^k = 1/n\\
2^k = n\\
log_2 2^k = log_2 n\\
k log_2 2 = log_2 n\\
k = log_2 n\\

(n > 0， k > 0)

n個のデータがあるとき，log n 回の分割でソートが完了するということです。

「分割された状態からマージする」と逆から考えることもできます。
(2 × 2 × 2 × 2 ...) と 2を何乗したら n になるか？

log n は「底の2を何乗したらnになるのか」を表しているのでそのままですね。

ここまでは，**バイナリサーチ（２分探索）**の計算量と同じです。

「k 回分割する」を「k 段の階層ができた」と言い換えます。

各段において，各要素はピボットと一回だけ比較されるので，一段あたりの計算量は O(n) となります。

したがって全体の計算量は

k × O(n)\\
= log_2 n × O(n)\\
⇒ O(n log_2 n)

毎回，範囲中の最小値または最大値をピボットに選んでしまうと k=n-1 となります。

よって，最悪計算量は以下になります。

(n-1) × O(n)\\
⇒ O(n^2)\\

おまけ（JavaScript でも実装してみる）

quickSort.js

/**
 * クイックソート
 * 
 * @param {Number} start 
 * @param {Number} end 
 * @param {Array} arr 
 */
const quickSort = (start, end, arr) => {

    const pivot = arr[Math.floor((start + end) / 2)];

    let [left, right] = [start, end];

    while (true) {
        while (arr[left] < pivot) {
            left++;
        }
        while (pivot < arr[right]) {
            right--;
        }
        if (right <= left){
            break;
        }
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }

    if (start < left-1) {
        quickSort(start, left-1, arr);
    }
    if (right+1 < end) {
        quickSort(right+1, end, arr);
    }

};

ソートする

// ソートする
const a = [3, 7, 1, 5, 6, 2, 4];
quickSort(0, a.length-1, a);

間違っている部分などあれば、ご指摘ください。