QuickSort.php

<?php

namespace App\Chapter4;

/**
 * Алгоритм быстрой сортировки испольует стратегию "разделяй и властвуй".
 * Функция получает на вход массив. Алгоритм имеет базовый случай,
 * когда массив состоит из 0 и 1 элемента, в этом случае массив
 * не надо сортировать, функция возвращает его как есть и рекурсивный случай,
 * когда массив должен разделяться до тех пор, пока не придёт к базовому случаю.
 * В рекурсивном случае необходимо выбрать опорный элемент, допустим это будет
 * первый элемент массива (худший случай O(n)), разделить массив на 2 подмассива:
 * элементы меньше опорного и элементы больше опорного, рекурсивно применить
 * быструю сортировку к 2 подмассивам. Время работы алгоритма зависит от выбора
 * опорного элемента: в среднем случае, когда опорный элемент берется из середины
 * составляет O(log n), в лучшем - когда берется случайный элемент: O (n log n).
 */
class QuickSort
{
    public function quickSort(array $array)
    {
        $lenght = count($array);

        if ($lenght < 2) {
            return $array;
        }

        $less = [];
        $greater = [];
        $pivot = $array[0];

        for ($item = 1; $item < $lenght; $item += 1) {
            if ($array[$item] < $pivot) {
                $less[] = $array[$item];
            } else {
                $greater[] = $array[$item];
            }
        }

        return array_merge($this->quickSort($less), [$pivot], $this->quickSort($greater));
    }
}