sorters

sorters.php

<?php
$arr = [10, 1, 3, 2, 4, 7, 6, 11];
$out = qsort($arr);
// $out = bsort($arr);
// $out = msort($arr);
print_r([$arr, $out]);


// quick sort
function qsort(array $array): array {
    if (\count($array) < 2) {
        return $array;
    }

    $left = $right = [];

    \reset($array);
    $pivotKey = \key($array);
    $pivot = \array_shift($array);

    foreach ($array as $k => $v) {
	    if ($v < $pivot) {
            $left[$k] = $v;
        } else {
            $right[$k] = $v;
        }
    }

    return [...qsort($left), ...[$pivotKey => $pivot], ...qsort($right)];
}



// bubble sort
function bsort(array $arr): array {
    $sorted = false;
    $length = \count($arr) - 1;
    while (!$sorted) {
        $sorted = true;
        for ($i = 0; $i < $length; ++$i) {
            if ($arr[$i] > $arr[$i + 1]) {
                $sorted = false;
                $tmp = $arr[$i];
                $arr[$i] = $arr[$i + 1];
                $arr[$i + 1] = $tmp;
            }
        }
    }
    
    return $arr;
}




// merge sort
function msort(array $array): array {
    $len = \count($array);
    if (1 === $len){
        return $array;
    }

    $mid = (int)($len / 2);
    $left = msort(\array_slice($array, 0, $mid));
    $right = msort(\array_slice($array, $mid));
    return merge($left, $right);
}

function merge(array $left, array $right): array {
    $combined = [];
    $totalLeft = \count($left);
    $totalRight = \count($right);
    $rightIndex = $leftIndex = 0;

    while ($leftIndex < $totalLeft && $rightIndex < $totalRight) {
        if ($left[$leftIndex] > $right[$rightIndex]) {
            $combined[] = $right[$rightIndex];
            $rightIndex++;
        } else {
            $combined[] = $left[$leftIndex];
            $leftIndex++;
        }
    }
    while ($leftIndex < $totalLeft) {
        $combined[] = $left[$leftIndex];
        $leftIndex++;
    }
    while ($rightIndex < $totalRight){
        $combined[] = $right[$rightIndex];
        $rightIndex++;
    }

    return $combined;
}