Zenn
Open2

PHPでクイックソート

Haskell
PHP
maroKanatanimaroKanatani

Haskellのような純粋関数型言語ライクなクイックソートを他の言語で書けないか考える。
（PHPと書いているがあまりこだわりはない。paiza.ioのデフォルトがPHPだから…くらいの感じ）

以下のような処理。

quickSort.hs
main = putStrLn $ show $ quickSort [6, 1, 4, 9, 3, 5, 8]

quickSort :: [Int] -> [Int]
quickSort [] = []
quickSort (x:xs) = (quickSort smaller) ++ [x] ++ (quickSort larger)
   where 
        smaller = [e| e <- xs, e < x] 
        larger =  [e| e <- xs, e > x]
maroKanatanimaroKanatani

PHPで書くと以下のような感じだろうか。（組み込み関数盛り沢山）

quickSort.php
<?php
print_r(quickSort([6, 1, 4, 9, 3, 5, 8]));

function quickSort($array) {
    if(count($array) === 0) {
        return [];
    }
    $pivot = $array[0];
    
    $smaller = quickSort(
        // array_filterだとfilter前のindexを保持するのでarray_valuesを噛ませてindexを振り直している
        array_values(
            array_filter($array, function($var) use ($pivot) {
                return $var < $pivot;
            })
        )
    );
    
    $larger = quickSort(
        // array_filterだとfilter前のindexを保持するのでarray_valuesを噛ませてindexを振り直している
        array_values(
            array_filter($array, function($var) use ($pivot) {
                return $var > $pivot;
            })
        )
    );
    return array_merge($smaller, [$pivot], $larger) ;
}