Быстрая сортировка - один из самых эффективных методов сортировки массива в информатике. Для более подробной информации у него есть собственная статья в Википедии.
В этой статье будет рассказано о реализации быстрой сортировки в JavaScript. Быстрая сортировка не встроена в JavaScript. Из-за метода sort в прототипе массива сортировка редко подвергается сомнению или оптимизируется в языке. Несмотря на это, быстрая сортировка по-прежнему является важным алгоритмом, по крайней мере, для понимания, независимо от того, используете ли вы его или нет.
Как это работает? 🤔
Quicksort работает, выбирая элемент из массива и обозначающий его как «точку поворота». Все остальные элементы в массиве разделены на две категории - они либо меньше, либо больше, чем этот элемент поворота.
Каждый из двух результирующих массивов (массив значений меньше точки поворота и массив значений больше точки поворота) затем проходит через тот же самый алгоритм. Выбирается точка поворота, а все остальные значения разделяются на два массива значений «меньше» и «больше».
В конце концов, подмассив будет содержать одно значение или вообще не содержать значения, так как больше не будет значений, с которыми его можно было бы сравнить. Все остальные значения были обозначены как «опорные точки» в какой-то предыдущий момент и не доходили до этого нижнего подмассива. В этот момент значения будут отсортированы, поскольку все значения были объявлены как меньшие или большие, чем все другие значения в массиве.
Как мы это реализуем? 💡
Поскольку метод прототипа Array sort использует собственный алгоритм сортировки, мы не можем использовать его для реализации быстрой сортировки. Мы должны создать функцию, которая получает массив для сортировки в качестве параметра и возвращает отсортированный массив.
Поскольку «значение» элемента в массиве может быть не сразу очевидным, мы должны предложить дополнительный параметр для компаратора. Сортировка строк или чисел встроена в JavaScript, а сортировка объектов - нет. Мы можем захотеть отсортировать коллекцию пользовательских объектов ({ name: 'Charles', age: 21 }) по возрасту.
Поскольку количество раз, которое мы можем разделить этот массив на меньшие / большие половины, может варьироваться в сторону бесконечности, мы хотим рекурсивно определить нашу логику, чтобы мы не повторяли наш код («выбрать точку поворота, разделить, повторить» ).
Вы можете использовать любой индекс в качестве точки поворота: первый, средний, последний, случайный. Если предположить, что данные отсортированы случайным образом, расположение точки поворота не повлияет на временную сложность. Я буду использовать последний индекс, потому что это то, что Википедия использует в своей демонстрационной графике, и приятно иметь визуальный элемент, совпадающий с кодом.
Массив перед шарниром делится на две части: меньше, чем шарнир спереди, больше, чем шарнир на конце. Наконец, сама точка поворота перемещается между двумя подмассивами, затем подмассивы сортируются с помощью того же алгоритма быстрой сортировки.
Мы создаем sortedArray как новый массив, чтобы не изменять исходный массив. Это не обязательно, но это хорошая практика.
Мы создаем recursiveSort как рекурсивную функцию, которая будет брать подмассив (от начального индекса до конечного индекса) и быстро его отсортировать, изменяя sortedArray по пути. Весь массив - это первый массив, передаваемый этой рекурсивной функции.
Наконец, возвращается отсортированный массив.
Функция recursiveSort имеет переменную pivotValue для обозначения значения нашей опорной точки и переменную splitIndex для обозначения индекса, ограничивающего массивы «меньше и больше». По идее, все значения «меньше» будут иметь индексы меньше splitIndex, а все значения «больше» будут иметь индексы больше splitIndex. splitIndex инициализируется началом подмассива, но, когда мы обнаруживаем значения, меньшие, чем значение поворота, мы соответствующим образом скорректируем splitIndex.
Мы пройдем по циклу все значения, не являющиеся сводными, перемещая те, которые меньше значения сводной таблицы, до начального индекса.
Мы перемещаем все значения, меньшие, чем значение поворота, в splitIndex, и все остальные значения оставляем там, где они есть (по умолчанию больше, чем splitIndex, поскольку индекс разделения начинается в начале подмассива).
После того, как подмассив был переупорядочен, мы перемещаем сам стержень в разделение, поскольку мы знаем, что он расположен между всеми значениями меньше и больше или равно.
Все значения слева (от start до splitIndex - 1) сортируются рекурсивно, а все значения справа (от splitIndex + 1 до end) сортируются рекурсивно. splitIndex теперь является значением поворота, которое больше не нужно сортировать.
Заключение 🔚
Вы можете найти код в этой статье, опубликованной в TypeScript на GitHub:
Вы также можете добавить этот код в свои проекты из NPM:
Если у вас есть какие-либо вопросы или важные идеи, пожалуйста, оставьте комментарий. Это быстро, просто и бесплатно!
Чтобы прочитать больше моих колонок или связаться со мной, вы можете найти меня в LinkedIn и Twitter или посмотреть мое портфолио на CharlesStover.com.
