Реализация быстрой сортировки на JavaScript

Перевод статьи Implementing Quicksort in JavaScript

Быстрая сортировка является одним из наиболее эффективных методов сортировки массива. Полное описания есть в статье на Вики.

В этой статье расскажем о реализации быстрой сортировки на JavaScript, т.к она не входит в JavaScript core. Из-за того, что на Array.prototype реализован метод sort, то сама сортировка редко подвергается сомнению или оптимизируется разработчиками. Несмотря на это, Quicksort по-прежнему является важным алгоритмом, по крайней мере, для понимания.

Как это работает? 🤔

Quicksort работает путем выбора элемента из массива и установки его в качестве «опорного». Все остальные элементы в массиве делятся на две категории - они меньше или больше, чем опорный элемент.

Каждый из двух результирующих массивов (с меньшими и с большими значениями) затем обрабатывается по тому же алгоритму. Выбирается опорный элемент, а все остальные значения разделяются на два массива - с меньшими и большими элементами.

В конце концов, подмассив будет содержать одно значение или не иметь значения вообще, так как больше не будет значений, с которыми его можно сравнивать. Все остальные значения были обозначены как «опорные» в некоторой предыдущей точке и не опускались до самого меньшего подмассива. В этот момент значения будут отсортированы, поскольку они теперь объявлены как меньшие или большие, чем все другие значения в массиве.

Как мы это реализуем? 💡

Поскольку Array.prototype.sort использует собственный алгоритм сортировки, мы не можем использовать его для реализации быстрой сортировки. Мы должны создать функцию, которая получает массив для сортировки в качестве параметра и возвращает отсортированный массив.

Поскольку «значение» элемента в массиве не может быть сразу очевидным, мы должны предложить необязательный параметр для компаратора. Сортировка строк или чисел встроена в JavaScript, а сортировка объектов - нет. Мы можем отсортировать коллекцию пользовательских объектов { name: 'Charles', age: 21 } по возрасту.

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

Вы можете использовать любой индекс в качестве положения опорного элемента: первый, средний, последний, случайный. Если предположить, что данные отсортированы случайным образом, расположение опорного элемента не повлияет на сложность по времени. Я буду использовать последний индекс, как это сделано в демо на вики.

Массив делится на две части: меньше, чем опорный элемент (в начале) и больше, чем опорный элемент (в конце). Наконец, сам опорный элемент перемещается между двумя вложенными массивами, а затем они сортируются по одному и тому же алгоритму быстрой сортировки.

Создадим sortedArray как новый массив, чтобы не изменять исходный массив. Это делать не обязательно, но это является хорошей практикой.

Мы создаем recursiveSort как рекурсивную функцию, которая будет брать подмассив (от начального индекса до конечного) и быстро сортировать его, изменяя по пути sortedArray. Первым рекурсивной функции передадим начальный массив. В конце вернем отсортированный массив.

В функции recursiveSort есть pivotValue - переменная для обозначения значения нашего опорного элемента и splitIndex - переменная для обозначения индекса, ограничивающего массивы меньших и больших элементов. Концептуально, все значения что меньше будут с индексами меньше, чем splitIndex и все большие значения будут с индексами больше чем splitIndex. splitIndex инициализируется началом подмассива, но, в процессе вычисления меньших значений, мы будем изменять splitIndex соответствующим образом.

Перебираем все неопорные значения, перемещая их на позицию перед начальным индексом.

Мы перемещаем все значения меньше опорного к splitIndex и оставляем все остальные значения там, где они были.

После переупорядочения под-массива мы перемещаем опроный элемент в splitIndex, так как мы знаем, что он расположен между значениями меньшими и большими (либо равеными).

Все значения слева (от начала до splitIndex - 1) рекурсивно отсортированы, как и все значения справа (от splitIndex + 1 до конца). splitIndex теперь само опорное значение, которое больше не нужно сортировать.

Заключение 🔚

Вы можете найти код из этой статьина GitHub:
https://github.com/CharlesStover/quicksort-js

Вы также можете добавить этот код в свой проект из NPM:
https://www.npmjs.com/package/@charlesstover/quicksort

Присоединяйтесь к нашим каналам FrontEndDev и Web Stack и моему личному блогу Sleepless Tech в Telegram, чтобы не пропустить самое интересное из мира Web!