Сбой алгоритма быстрой сортировки с ошибкой переполнения стека

Question

Я пытался реализовать алгоритм QuickSort от Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л. Ривеста, Клиффорда Стейна - Введение в алгоритмы, третье издание - 2009 * Раздел 7.1

в JavaScript.

Итак, вот моя реализация:

function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function partition(arr, left = 0, right = arr.length - 1) {
    let pivot = arr[right];
    let i = left - 1;
    let j;

    for (j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }

    swap(arr, i + 1, right);
    return i + 1;
}

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return arr;
    const p = partition(arr, left, right);
    quickSort(arr, left, p - 1);
    quickSort(arr, p + 1, right);
    return arr;
}

Проблема этого кода в том, что он не работает с ошибкой stackoverflow, если я передаю уже отсортированный массив с длиной> 10 000

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

Answer 1

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

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

Один из способов выбрать опору, чтобы избежать этого, состоит в том, чтобы выбрать опору случайным образом. Это делает маловероятным (но не невозможным) попадание в худший вариант, и поэтому в среднем будет работать хорошо. У него есть уязвимость, заключающаяся в том, что если кто-то знает алгоритм случайных чисел и начальное число, которое вы используете, то он может создать массив, который приведет вас к худшему случаю.

Идеальной опорой является среднее значение. Поэтому один из подходов - попытаться найти медиану или приблизиться к ней. Например, вы можете взять выборку из 3 случайных элементов массива и использовать медиану этих 3 в качестве своей оси. Это вряд ли будет точно медиана, но достаточно хорошо в большинстве случаев. Вы можете выбрать больше, чтобы получить лучшее приближение к медиане, но затем вы тратите больше времени на поиск точки, чем просто продвигаясь вперед по алгоритму; это немного компромисс.

Answer 2

происходит сбой с ошибкой переполнения стека, если я передаю уже отсортированный массив длиной> 10 000

Проблема, как обычно с быстрой сортировкой, заключается в выборе элемента поворота . Вы берете pivot = arr[right], поэтому в уже отсортированном массиве функция partition разделит диапазон на [left, right-1] и [right, right]. Ваше двоичное дерево рекурсивных вызовов вырождается в список, и 10 000 рекурсивных вызовов слишком много для стека.

В качестве альтернативы можно выбрать случайный индекс разворота (что маловероятно, но не невозможно) или найти среднее значение.

Answer 3

Независимо от того, какую опору вы выберете, всегда есть вероятность переполнения стека. Чтобы избежать этого, вот пример функции быстрой сортировки C ++, которая использует рекурсию для меньшей части, а затем возвращается к циклу для больших частей. Это ограничивает пространство стека O (log (n)), но сложность времени в худшем случае остается на уровне O (n ^ 2).

void QuickSort(uint64_t a[], int lo, int hi)
{
    while (lo < hi){
        uint64_t p = a[hi];
        int i = lo;
        for (int j = lo; j < hi; ++j){
            if (a[j] < p){
                std::swap(a[j], a[i]);
                ++i;
            }
        }
        std::swap(a[i], a[hi]);
        if(i - lo <= hi - i){
            QuickSort(a, lo, i-1);
            lo = i+1;
        } else {
            QuickSort(a, i+1, hi);
            hi = i-1;
        }
    }
}