Быстрая сортировка на PHP

Вероятно самым популярным алгоритмом сортировки в общем случае является быстрая сортировка.

    Причины тому две:
  • 1) Хорошее среднее время работы n lg n и небольшой постоянный множитель n (то есть код не нагружен)
  • 2) Малое потребление памяти

Минусы правда тоже есть, худшее время работы составляет n^2, однако на практике добиться этого сложно, тем более есть ряд оптимизаций, которые существенно минимизируют шанс наихудшего времени, о некоторых оптимизациях я упомяну.

Еще один минус - сортировка по умолчанию не устойчива, но это исправляется довольно просто.

В общем в итоге получаем один из самых быстрых алгоритмов сортировки на практике.

    Общая идея алгоритма проста и так же проповедуют парадигму "разделяй и властвуй", как и сортировка слиянием.
  • 1) В исходном массиве берется так называемый опорный элемент.
  • 2) Массив делится вокруг этого опорного элемента за линейное время.
    Слева от опорного элемента находятся элементы меньшие либо равные ему, а справа находятся элементы больше опорного.
  • 3) Далее массив делится на две части по опорному элементу и для каждой части рекурсивно продолжается деление и сортировка по новому опорному элементу, и так пока не дойдем до единичного массива, после чего выходим из рекурсии и получаем отсортированный массив.

Как и сортировка слиянием состоит из двух функций.
Первая рекурсивная делит массив по опорному элементу, а вторая линейная сортирует подмассивы по новому опорному элементу и возвращает его функции деления.
Я приведу процедурный подход к реализации кода.

function quickSort(&$mas, $s, $f)
{	
    if($s < $f)
    {
        $q = partition($mas, $s, $f);
        quickSort($mas, $s, $q-1);
        quickSort($mas, $q+1, $f);
    }
}

Принимаем на вход исходный массив, индекс начала массива и индекс конца массива.

Далее проверяем не достигли ли мы условия выхода из рекурсии, то есть когда подмассив равен одному значению.

Если у нас на вход массив с более, чем одним элементом, то вызываем для него функцию разделения-сортировки, функция возвращает опорный элемент и сортирует массив mas по нему.

Далее рекурсивно продолжаем вызывать сами себя для все более мелких подмассивов.

Теперь посмотрим на функцию portition, она более интересная.

function partition(&$mas, $s, $f)
{
    $q = $s;
		
    for($i=$s; $i < $f; $i++)
    {
        if($mas[$i] <= $mas[$f])
        {
            $buf = $mas[$i];
            $mas[$i] = $mas[$q];
            $mas[$q] = $buf;
            $q++;
        }
    }
		
    $buf = $mas[$q];
    $mas[$q] = $mas[$f];
    $mas[$f] = $buf;
		
    return $q;
}

На вход так же принимаем массив, начало и конец интервала с которым будем работать. В качестве опорного элемента у нас будет f - конечный индекс.

    Логика сортировки заключается в следующем. Создаются виртуальные области области массива:
  • 1) Левая область MAS[s...q-1] - со значениями меньше либо равными опорному элементу.
  • 2) Правая область MAS[q...i-1] - со значениями больше опорного элемента.
  • 3) Область неизвестности MAS[i...f-1] - со значениями чье положение пока не понятно
  • 4) Опорный элемент MAS[f]

Изначально весь массив находится в области неизвестности, то есть нужно определить каждый элемент.
При входе в цикл мы проверяем каждый i-ый элемент, тем самым уменьшая область неизвестности и расширяя левые и правые области. При нахождении элемента, который меньше либо равен опорному мы добавляем его в левую часть, и уменьшаем границу правой части.

После выхода из цикла мы меняем местами крайний левый элемент в правой части с опорным элементом, тем самым делая опорный элемент находящемся посередине.

В качестве защиты от плохих данных опорный элемент можно брать случайным каждый раз.

При массиве в 1 000 000 элементов заполнеными случайными значениями от 0 до 1 000 000, быстрая сортировка работает на 20% быстрее, чем сортировка слиянием.

Однако если снизить вариативность элементов например от 1 до 100, то вы можете не дождаться пока выполнится быстрая сортировка...
Она хорошо работает, когда опорный элемент находится примерно посередине разделяемого массива, а с малым диапазоном значений это получается не очень хорошо.


comments powered by Disqus