はじめに
完全に乗り遅れてますが、今話題のクイックソートをPHPで実装してみます。
PHPに組み込みのsort関数があるのはもちろん知ってます。
クイックソートの概要
クイックソートというのはソートのアルゴリズムの１つで、他のソート法より計算量が少なく高速にソートを行えます。（厳密には他のソート法と同じ計算量になる場合もあります。）
クイックソートのロジックについては調べれば分かりやすい説明がたくさん出てくるので、今回書いたコードの簡単な手順をざっくりまとめておきます。
- 配列の要素が１つの場合は、それを返す。
- 配列の中からピボット（軸となる要素）を適当に決める。
- その要素より大きいグループと小さいグループに分ける。 （ピボットと同じ大きさのものはどちらかに）
- 各グループで1,2,3を再帰的に繰り返す。
- 4の結果を小さいグループ、最初のピボット、大きいグループの順に並べる。
ところでPHP組み込みのsort関数は、どうやら内部クイックソートを行っているようです。
注意: PHP の大半のソート関数と同様、sort() は » Quicksort でそれを実装しています。 ピボットは、既にソート済みの部分に対して時間的に最適なところを選択します。 しかしこれはあくまでも内部の実装の話なので、これに依存したコードを書いてはいけません。
実行環境
PHP 8.0.11
実際にやってみた
/**
* quick sort
* @param array<int, int> $numbers
* @return array
*/
function quickSort(array $numbers): array
{
// 要素数が１つの場合は並び替え不要
if (count($numbers) < 2) {
return $numbers;
}
// 先頭の要素をピボットとして取り出す。
$pivot = array_shift($numbers);
// 初期化
$left = [];
$right = [];
// 要素の大きさがピボット以下のものと大きいものとでわけっこ
foreach ($numbers as $num) {
if ($num <= $pivot) {
$left[] = $num;
} else {
$right[] = $num;
}
}
// それぞれで再帰的に処理を繰り返す
$left = quickSort($left);
$right = quickSort($right);
return array_merge($left, [$pivot], $right);
}
一応テストも
public function testQuickSort(): void
{
$this->assertSame(
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
quickSort([9, 1, 8, 2, 7, 3, 6, 4, 5, 10])
);
$this->assertSame(
[2, 3, 3, 4, 4, 5, 5, 6, 7, 10],
quickSort([3, 4, 5, 2, 7, 3, 6, 4, 5, 10])
);
}
OK (1 test, 2 assertions)
無事通りました。
ちなみにピボットをどのように選択するかで、計算量が変わってくるようです。
今回は先頭の要素をピボットにしてますが、計算量を考慮したときにどうやら悪手みたいですね。他のピボットの選択方法としては、
- 配列から要素を複数ランダムに選び、それらの中央値をピボットにする
- ランダムに選ぶ（人為的に最悪ケースになるのを防げる）
等があるようです。
また、与えられた配列を処理の前にランダムに並び替えることによって計算量が最悪のケースになる可能性を抑えることもできるようです。
PHPのsort関数では、この辺りの最適化もやってくれているようですね。
さいごに
組み込み関数への感謝を忘れない。