Автор оригинала: Abhilash Kakumanu.
Вступление
Сортировка относится к организации элементов списка в определенном порядке (численное или буквенное значение). Сортировка обычно используется в тандеме с поиском.
На протяжении многих лет были разработаны многие сортировки алгоритмов, и один из самых быстрых на сегодняшний день Quicksort Отказ
QuickSort использует стратегию Divide-and-Conquer, чтобы сортировать данный список элементов. Это означает, что алгоритм нарушает проблему в подгруппы, пока они не станут достаточно простыми, чтобы решить напрямую.
Алгоритмически это может быть реализовано либо реюрсивно, либо итеративно. Однако рекурсивный подход более естественен для этой проблемы.
Понимание логики за Quicksort
Давайте посмотрим, как работает Quicksort:
- Выберите элемент массива. Этот элемент обычно называется Удар Отказ Чаще всего этот элемент либо первый или последний элемент в массиве.
- Затем переставьте элементы массива, чтобы все элементы слева от поворота меньше, чем у поворота, и все элементы вправо больше, чем у поворота. Шаг называется разбиение Отказ Если элемент равен повороту, это не имеет значения, на какую сторону она идет.
- Повторите этот процесс индивидуально для левой и правой стороны поворота, пока массив не будет отсортирован.
Давайте понять эти шаги дальше, пройдя через пример. Рассмотрим массив несортированных элементов [7, -2, 4, 1, 6, 5, 0, -4, 2] Отказ Мы выберем последний элемент, чтобы быть поворотом. Пошаговая поломка массива будет такой, как показано на рисунке ниже:
Элементы, которые были выбраны в качестве поворота на одном этапе алгоритма, имеют цветную контур. После разбиения элементы поворота всегда находятся в правильных позициях в массиве.
Массивы, которые имеют смелый черный план, представляют собой конец этой конкретной рекурсивной ветви, поскольку мы закончили с массивом, содержащим только один элемент.
Мы можем увидеть полученную сортировку этого алгоритма, просто пройдя через самый низкий элемент в каждом «колонне».
Реализация QuickSort в JavaScript
Как мы могли видеть, основой этого алгоритма является разбиение шаг. Этот шаг такой же независимо от того, используете ли мы рекурсивный или итеративный подход.
С учетом этого давайте сначала напишу код на раздел () массив:
function partition(arr, start, end){
// Taking the last element as the pivot
const pivotValue = arr[end];
let pivotIndex = start;
for (let i = start; i < end; i++) {
if (arr[i] < pivotValue) {
// Swapping elements
[arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
// Moving to next element
pivotIndex++;
}
}
// Putting the pivot value in the middle
[arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]]
return pivotIndex;
};
Здесь мы принимаем последний элемент в качестве поворота. Мы используем переменную Pivotindex Чтобы отслеживать положение «среднего», где все элементы слева меньше, и все элементы справа являются больше, чем pivotvalue Отказ
В качестве последнего шага мы поменяем поворачивание, что является последним элементом в нашем случае с Pivotindex Отказ Итак, в итоге наш элемент поворота в конечном итоге в «середине». Со всеми элементами меньше, чем у поворота к левой стороне этого, и все элементы, превышающие или равно поворачиванию справа от поворота.
Рекурсивная реализация
Теперь, когда у нас есть раздел () Функция, мы должны рекурсивно разрушать эту проблему вниз и применить логику разделения, чтобы сделать оставшиеся шаги:
function quickSortRecursive(arr, start, end) {
// Base case or terminating case
if (start >= end) {
return;
}
// Returns pivotIndex
let index = partition(arr, start, end);
// Recursively apply the same logic to the left and right subarrays
quickSort(arr, start, index - 1);
quickSort(arr, index + 1, end);
}
В этой функции мы начинаем с разделения массива. После этого мы разделяем как левые, так и правые подвески. Мы повторяем этот процесс до тех пор, пока способ получает массив, который не пустой или имеет более одного элемента.
Это связано с тем, что пустые массивы и массивы только с одним элементом считаются отсортированными.
Давайте проверим этот код на нашем оригинальном примере, позвонив:
array = [7, -2, 4, 1, 6, 5, 0, -4, 2] quickSortRecursive(array, 0, array.length - 1) console.log(array)
Это даст нам выход:
-4,-2,0,1,2,4,5,6,7
Итеративная реализация
Как мы упоминали ранее, рекурсивный подход к QuickSort гораздо более интуитивно. Однако реализация Quicksort итеративно представляет собой относительно общий вопрос интервью для инженеров программного обеспечения.
Как и в случае с большинством рекурсивных итеративных преобразований, первое, что должно прийти к уму, использует стек для симуляции рекурсивных вызовов. Это сделано, чтобы мы могли повторно использовать некоторые из рекурсивной логики, с которой мы знакомы, и используем его в итеративной настройке.
Нам нужно как-то отслеживать, какие несортированные подлочки мы оставили. Один из способов сделать это, чтобы просто сохранить «пары» элементов в стеке, представляющих Начать и конец данного несортированной подложки.
JavaScript не имеет явного структуры данных стека, но массивы поддерживают push () и POP () Функции. Они не поддерживают PEEK () Функция, однако, поэтому нам придется вручную проверить верхнюю часть стека, используя Stack [Stack.Length - 1] Отказ
Мы будем использовать то же самое Раздел Функция, как мы сделали для рекурсивного подхода. Давайте посмотрим, как написать часть QuickSort:
function quickSortIterative(arr) {
// Creating an array that we'll use as a stack, using the push() and pop() functions
stack = [];
// Adding the entire initial array as an "unsorted subarray"
stack.push(0);
stack.push(arr.length - 1);
// There isn't an explicit peek() function
// The loop repeats as long as we have unsorted subarrays
while(stack[stack.length - 1] >= 0){
// Extracting the top unsorted subarray
end = stack.pop();
start = stack.pop();
pivotIndex = partition(arr, start, end);
// If there are unsorted elements to the "left" of the pivot,
// we add that subarray to the stack so we can sort it later
if (pivotIndex - 1 > start){
stack.push(start);
stack.push(pivotIndex - 1);
}
// If there are unsorted elements to the "right" of the pivot,
// we add that subarray to the stack so we can sort it later
if (pivotIndex + 1 < end){
stack.push(pivotIndex + 1);
stack.push(end);
}
}
}
Давайте проверим этот код на нашем примере, позвонив:
ourArray = [7, -2, 4, 1, 6, 5, 0, -4, 2] quickSortIterative(ourArray) console.log(ourArray)
Мы получаем ожидаемый результат:
-4,-2,0,1,2,4,5,6,7
Визуализация быстрой сортировки
Когда дело доходит до сортировки алгоритмов, его всегда приятно визуализировать их. Это просто помогает нам “увидеть их в действии Вот пример того, как работает алгоритм Quicksort:
Источник: Википедия
В этом случае поворот также принимается в качестве последнего элемента. После того, как данный массив разделен, левая сторона рекурсивно пропала до тех пор, пока она полностью не отсортирована. Тогда алгоритм приходит на правую сторону и делает сортировку.
Эффективность быстрой сортировки
Теперь, когда мы знаем, как реализовать алгоритм Quicksort, давайте обсудим время и космическую сложность. Сложность худшего случая быстрого рода – O (n 2 ) Отказ Средняя сложность времени Case – O (nlogn) Отказ Худший случай обычно избегают, используя рандомизированную версию QuickSort.
Слабое пятно алгоритма Quicksort – выбор поворота. Выбирая плохой поворот (тот, который больше, чем/меньше, чем большинство элементов) каждый раз, даст нам ухудшение сложности времени. В то время как неоднократно выбирая поворот, который имеет примерно равное количество элементов, которые меньше/больше, чем пивот, даст нам временную сложность O (nlogn) Отказ
QuickSort является одним из тех алгоритмов, где среднее время выполнения на самом деле важно. Эмпирически, было замечено, что QuickSort имеет тенденцию иметь O (nlogn) Во время выполнения независимо от того, чтобы выбирать стратегию.
Кроме того, когда дело доходит до космической сложности, QuickSort не принимает никакого дополнительного места (исключая пространство, зарезервированное для рекурсивных вызовов). Эти виды алгоритмов технически называются как на месте алгоритмы. Нам не нужно дополнительное пространство, потому что мы выполняем операцию на одном и том же массиве.
Заключение
В этой статье мы прошли теорию позади Quicksort, а затем реализовали ее рекурсивно и итеративно используя JavaScript.