PHPでクイックソートというものをやってみた

php algorithm

一般的に最も高速なソートのアルゴリズムらしい。

アルゴリズム

1. 適当な数（ピボットという）を選択する （この場合はデータの総数の中央値が望ましい）
2. ピボットより小さい数を前方、大きい数を後方に移動させる （分割）
3. 二分割された各々のデータを、それぞれソートする

実装

<?php
function quicksort($array) {
    if (count($array) <= 1) {
        return $array;
    }
    $pivot = array_shift($array); // ピボットの選択

    $left = $right = array();
    foreach ($array as $value) {
        if ($value < $pivot) {
            $left[]  = $value;　// ピボットより小さい数は左
        } else {
            $right[] = $value;  // ピボットより大きい数は右
        }
    }
    // 左右のデータを再帰的にソートする
    return array_merge(quicksort($left), array($pivot), quicksort($right));
}

実行

<?php
$array = array(
    6, 4, 3, 7, 8, 5, 2, 9, 1,
);
$array = quicksort($array);
var_dump($array); // 1, 2, 3, 4, 5, 6, 7, 8, 9

参考