array_filter と create_function でクイックソート

まーPHP 5.2.x 系以前でこういうことやろうとすると当然create_functionなどというひどいものを使わないといけなかったり。つーか、配列の結合が、+ と array_merge のどっちつかうかは何年PHPつかってても身に付かんな。添字配列と連想配列が一緒くたに扱われるPHPだからまあしかたないといえばしかたないんだけど。

<?php

function qsort(Array $list) {
    if (count($list) == 0) {
        return array();
    }   

    $pivot = array_shift($list);

    return array_merge(qsort(array_filter($list, create_function('$x', 'return ($x < ' . $pivot . ');')))
        , array($pivot)
        , qsort(array_filter($list, create_function('$x', 'return ($x >= ' . $pivot . ');'))));
}

function print_array(Array $a) {

    foreach($a as $v) {
        echo "  $v\n";
    }   
    echo "\n";
}

$array = array();
foreach(range(1,10000) as $v) {
    $array[] = mt_rand();
}
print_array(qsort($array));

  34256 
  42274 
  363496
  430324
  811500
  1414511
  2155767
  2158085
  2362754
  2559003
  2687188
...
  2145905351
  2146041602
  2146179876
  2146340678
  2146458622
  2146688188
  2146999472
  2147473020

ちなみに実行時間は、1万の乱数で、乱数配列生成時間も含めて、

% time php qsort.php >/dev/null
php qsort.php > /dev/null  0.61s user 0.05s system 98% cpu 0.664 total

こんなかんじ。