Статья подготовлена для студентов курса «Backend разработчик на PHP» в образовательном проекте OTUS.
В этой статье поговорим о Быстрой сортировке (quicksort). Почему именно она? На мой взгляд, эта сортировка отлично подходит для решения повседневных задач. Ниже я приведу принцип данной сортировки и две её реализации — на PHP и JavaScript.
Wiki говорит, что быстрая сортировка была придумана английским информатиком Чарльзом Хоаром в 1960 году.
Сортировка работает следующим образом:
1) Выбирается опорный элемент. Его можно выбрать случайно, обозначить его последним или средним — это всё не будет влиять на эффективность.
2) Массив перестраивается следующим образом: слева от опорного алгоритма находятся элементы, которые меньше его или равны ему, справа — элементы, которые больше него.
На каждой итерации мы выполняем следующие действия
а) выбираем два индекса low и high, равные крайнему левому и крайнему правому элементам входного массива;
б) вычисляем индекс опорного элемента middle;
в) увеличиваем low последовательно до тех пор, пока элемент с индексом low не будет больше или равен опорному;
г) уменьшаем high последовательно до тех пор, пока элемент с индексом high не будет меньше или равен опорному;
д1) если low = high, то мы нашли середину входного массива;
д2) если low < high, то мы меняем эти элементы местами.
3) Далее мы начинаем рекурсивно упорядочивать полученные два массива из элементов, лежащих справа и слева от опорного элемента соответственно.
4) Рекурсивное обращение продолжается до тех пор, пока все входные наборы не будут содержать один или два элемента.
Данная сортировка — это глубокое улучшение сортировки «пузырьком». Она является одним из самых быстродействующих алгоритмов сортировки общего назначения.
От теории к практике
Рассмотрим реализацию на PHP. В функцию quickSort передаём три параметра: массив (по ссылке), левую границу и правую границу. Сразу же определяем $middle — опорный элемент. Мы возьмём в качестве него средний элемент массива. Далее начинаем два циклических обхода справа и слева до нахождения бОльшего и мЕньшего элементов относительно опорного, перебрасываем их. Затем рекурсивно вызываем quickSort для двух полученных массивов. Здесь всё достаточно просто, а код функции будет выглядеть вот так:
На JavaScript функция не будет сильно отличаться структурно, однако имеются некоторые моменты, касающиеся самого языка. В определении опорного элемента следует принудительно использовать округление, дабы не получить дробный индекс. Массив передается по ссылке по умолчанию, так что хитрить с приведением типов не следует.
Рабочий пример сортировки можно посмотреть тут.
