В своей последней статье я решил погрузиться в алгоритмическую парадигму «Разделяй и властвуй», и то, что я нашел, было довольно интересным!
Во-первых, я понял важность возможности сортировать массивы в программировании. Это обычная задача, которую вы пытаетесь выполнить. Как я объяснял в своей предыдущей статье, во многих языках программирования есть встроенные функции для сортировки, такие как sort() в JavaScript, но мы, программисты, не всегда хотим выбирать легкий путь, мы хотим знать, как это делается!
Когда я узнал об алгоритмах «разделяй и властвуй», я понял еще одну вещь: насколько невероятно гениальна их идея! Давайте еще раз пройдемся по шагам алгоритма «разделяй и властвуй».
Разделяй и властвуй
Разделяй и властвуй — это парадигма программирования, которую используют алгоритмы сортировки слиянием и быстрой сортировки. Это алгоритм, основанный на рекурсии, и он разбит на 3 основных этапа:
- Разделите проблему на подзадачи, которые являются просто меньшими экземплярами исходной проблемы.
- Победите подзадачи, решая их рекурсивно. Если проблема достаточно мала, то это основная проблема.
- Объедините решения подзадач с решением исходной задачи.
Вот как это выглядит:
Довольно крутая штука! Я аплодирую математику, придумавшему этот алгоритм!
Теперь давайте более подробно рассмотрим QuickSort и что это такое.
Быстрая сортировка
Быстрая сортировка похожа на сортировку слиянием, но есть несколько отличий. Сортировка слиянием разбита на 3 этапа:
- Разделять
- Завоевывать
- Объединить
Большая часть работы при сортировке слиянием выполняется на этапе Объединение. В быстрой сортировке работа выполняется на этапе Разделить, а на этапе Объединить практически ничего не делается!
Алгоритм быстрой сортировки делает то же самое, что и сортировка слиянием: разделяй, властвуй и комбинируй, но, по моему личному мнению, быстрая сортировка немного более запутанна, чем сортировка слиянием, поэтому я собираюсь разобрать, что происходит на каждом этапе:
- Выберите элемент внутри массива, выбранный вами элемент должен быть либо первым, либо последним элементом в массиве. Этот элемент обычно называют основным элементом.
- Переставьте элементы массива так, чтобы все элементы, меньшие, чем опорная, были слева, а все элементы, большие, чем опорная, были справа. Этот шаг называется разметка. Важно отметить, что если элемент равен стержню, не имеет значения, на какой стороне массива он находится.
- Повторяйте шаги 2 и 3 по отдельности для левой и правой сторон оси, пока массив не будет отсортирован.
Вот визуальное:
Теперь, когда мы хорошо понимаем, что такое алгоритм QuickSort, давайте посмотрим, как мы можем реализовать его с помощью JavaScript!
Раздел()
Во-первых, мы собираемся создать функцию partition(), чтобы позаботиться о нашем шаге разделения в алгоритме:
В приведенной выше функции мы берем последний элемент в качестве опорного. Мы используем переменную pivotIndex для отслеживания «средней» позиции, где все элементы слева меньше, а все элементы справа больше, чем pivotIndex. >
На последнем этапе мы меняем опорную точку (которая в нашем случае является последним элементом) на pivotIndex. В конце концов, наш сводной элемент оказывается в «середине», где элементы меньше pivotIndex слева, а элементы больше pivotIndex ближе к краю. правильно.
Быстрая сортировка()
Теперь, когда у нас есть функция partition(), нам нужно применить ее к нашему рекурсивному алгоритму, чтобы повторять процесс до тех пор, пока массив не будет отсортирован. Здесь я напишу функцию quickSort() для выполнения этой задачи:
Здесь мы начинаем с разделения массива. После этого мы продолжаем разбивать как левый, так и правый подмассивы. Мы повторяем процесс до тех пор, пока метод не получит пустой массив или массив, содержащий только один элемент. Это связано с тем, что пустой массив или массив, содержащий только один элемент, считается отсортированным.
Теперь давайте проверим это!
После написания этого у вас должен быть отсортированный массив в вашей консоли, который выглядит так:
Удивительный!
Спасибо, что нашли время прочитать эту статью, и, надеюсь, вы узнали что-то об алгоритме QuickSort и парадигме «разделяй и властвуй». Я продолжу свое путешествие по программированию, изучая новые парадигмы и алгоритмы, и я надеюсь, что вы тоже! Удачного кодирования!
