10.10.2020 в 15:20

Быстрая сортировка в JavaScript

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

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

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

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

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

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

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

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

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

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

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

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

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

Теперь, когда у нас есть функция 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

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

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

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

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

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

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

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

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

Вывод

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

Источник:

Quicksort in JavaScript

#JavaScript

7580

-1

Войти на сайт