クイックソートとは
**分割統治法（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での実装
/**
* クイックソート
* 渡された配列を破壊的に変更します
*
* @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 でも実装してみる）
/**
* クイックソート
*
* @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);
間違っている部分などあれば、ご指摘ください。