2.quicksort.md

QuickSort

Links

• https://medium.com/devschacht/nicholas-c-zakas-computer-science-in-javascript-quicksort-afa07c0a47f0

JavaScript

    function swap(items, firstIndex, secondIndex) {
        const temp = items[firstIndex];
        items[firstIndex] = items[secondIndex];
        items[secondIndex] = temp;
    }

    function partition(items, left, right) {
        var pivot = items[Math.floor((right + left) / 2)],
            i = left,
            j = right;

        while (i <= j) {
            while (items[i] < pivot) {
                i++;
            }
            while (items[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(items, i, j);
                i++;
                j--;
            }
        }
        return i;
    }

    function quickSort(items, left, right) {
        var index;
        if (items.length > 1) {
            index = partition(items, left, right);
            if (left < index - 1) {
                quickSort(items, left, index - 1);
            }
            if (index < right) {
                quickSort(items, index, right);
            }
        }
        return items;
    }

    var items = [2, 5, 1, 3, 7, 2, 3, 8, 6, 3];
    // first call
    console.log(quickSort(items, 0, items.length - 1));

<?php

declare(strict_types = 1);

function merge(array $arr)
{
    function swap(array &$array, int $firstIndex, int $endIndex)
    {
        $temp = $array[$firstIndex];
        $array[$firstIndex] = $array[$endIndex];
        $array[$endIndex] = $temp;
    }

    function partition(array &$arr, int $start, int $end)
    {
        $pivot = $arr[(int) (($start + $end) / 2)];
        $i = $start;
        $j = $end;
        while ($i <= $j) {
            while ($arr[$i] < $pivot) {
                ++$i;
            }
            while ($arr[$j] > $pivot) {
                --$j;
            }

            if ($i <= $j) {
                swap($arr, $i, $j);
                ++$i;
                --$j;
            }
        }

        return $i;

    }

    function quickSort(array &$arr, int $start, int $end)
    {
        if (\count($arr) > 1) {
            $index = partition($arr, $start, $end);

            if ($start < $index - 1) {
                quickSort($arr, $start, $index - 1);
            }

            if ($index < $end) {
                quickSort($arr, $index, $end);
            }
        }

        return $arr;
    }

    return quickSort($arr, 0, \count($arr) - 1);
}

var_dump(merge([2, 5, 1, 3, 7, 2, 3, 8, 6, 3]));