Вступление

Сортировка относится к расположению элементов списка в определенном порядке (числовом или алфавитном). Сортировка обычно используется вместе с поиском.

За прошедшие годы было разработано множество алгоритмов сортировки, и одним из самых быстрых на сегодняшний день является Quicksort .

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

Алгоритмически это может быть реализовано рекурсивно или итеративно. Однако для этой задачи более естественен рекурсивный подход.

Понимание логики быстрой сортировки

Давайте посмотрим, как работает Quicksort:

1. Выберите элемент массива. Этот элемент обычно называют стержнем . Чаще всего этот элемент является первым или последним элементом массива.
2. Затем переставьте элементы массива так, чтобы все элементы слева от оси были меньше, чем точка поворота, а все элементы справа были больше, чем точка поворота. Шаг называется разбиением . Если элемент равен оси поворота, не имеет значения, с какой стороны он идет.
3. Повторите этот процесс индивидуально для левой и правой стороны поворота, пока массив не будет отсортирован.

Давайте разберемся с этими шагами дальше на примере. Рассмотрим массив несортированных элементов [7, -2, 4, 1, 6, 5, 0, -4, 2] . Мы выберем последний элемент в качестве стержня. Пошаговая разбивка массива будет такой, как показано на изображении ниже:

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

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

Мы можем увидеть итоговую сортировку этого алгоритма, просто перебрав самый нижний элемент в каждом «столбце».

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

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

Имея это в виду, давайте сначала напишем код для partition() массива:

 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 , которая в нашем случае является последним элементом, на pivotIndex. Итак, в конце концов, наш опорный элемент окажется в «середине». Со всеми элементами, меньшими, чем точка поворота, слева от нее, и всеми элементами, которые больше или равны оси поворота справа от нее.

Рекурсивная реализация

Теперь, когда у нас есть partition() , мы должны рекурсивно решить эту проблему и применить логику разделения, чтобы выполнить оставшиеся шаги:

 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 - довольно частый вопрос для инженеров-программистов.

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

Нам нужно как-то отслеживать, какие несортированные подмассивы у нас остались. Один из способов сделать это - просто сохранить «пары» элементов в стеке, представляющие start и end данного несортированного подмассива.

JavaScript не имеет явной структуры данных стека, но массивы поддерживают функции push() и pop() . Однако они не поддерживают peek() , поэтому нам придется вручную проверять вершину стека, используя stack[stack.length - 1] .

Мы будем использовать ту же partition что и для рекурсивного подхода. Давайте посмотрим, как написать часть 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 

Визуализация быстрой сортировки

Когда дело доходит до алгоритмов сортировки, всегда полезно визуализировать их. Это просто помогает нам «увидеть» их в действии. Вот пример того, как работает алгоритм быстрой сортировки:

{.ezlazyload}

[Источник: Википедия.]{.small}

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

Эффективность быстрой сортировки

Теперь, когда мы знаем, как реализовать алгоритм быстрой сортировки, давайте обсудим временную и пространственную сложность. Наихудшая временная сложность быстрой сортировки составляет O (n ^2^ ) . Средняя временная сложность случая составляет O (nlogn) . Наихудшего случая обычно избегают, используя рандомизированную версию Quicksort.

Слабым местом алгоритма Quicksort является выбор точки поворота. Выбор плохого поворота (тот, который больше / меньше большинства элементов) каждый раз даст нам наихудшую временную сложность. При многократном выборе стержня, который имеет примерно равное количество элементов, которые меньше / больше, чем стержень, мы получим временную сложность O (nlogn) .

Быстрая сортировка - один из тех алгоритмов, для которых действительно важно среднее время выполнения. Опытным путем было замечено, что Quicksort имеет тенденцию иметь время выполнения O (nlogn) независимо от стратегии выбора точки поворота.

Кроме того, когда дело доходит до сложности пространства, Quicksort не занимает лишнего места (за исключением места, зарезервированного для рекурсивных вызовов). Эти виды алгоритмов технически называются оперативными алгоритмами. Нам не нужно дополнительное пространство, потому что мы выполняем операцию с тем же массивом.

Заключение

В этой статье мы рассмотрели теорию быстрой сортировки, а затем реализовали ее рекурсивно и итеративно с помощью JavaScript.