Quicksort генерирует код выхода -1073741571 (0xC00000FD) при попытке отсортировать большой отсортированный контейнер

Question

Я пытаюсь реализовать работающую быструю сортировку, вариант Lomuto.Я использую псевдокод из Википедии.https://en.wikipedia.org/wiki/Quicksort

void quickSortLomuto(int *first, int *last) {
    if(first < last){
        int *pivot= partitionLomuto(first,last);
        quickSortLomuto(first, pivot- 1);
        quickSortLomuto(pivot+ 1,last);
    }
}
int* partitionLomuto(int* first, int* last) {
    int pivot = *last;
    int *i = first;
    for(int* j = first;j <= last -1;j++){

        if(*j < pivot){
            std::swap(*i,*j);
            i++;
        }
    }
    std::swap(*i,*last);
    return i;
}

Отлично работает для больших контейнеров со случайными числами.он ломается и генерирует код выхода -1073741571 (0xC00000FD) для отсортированных контейнеров.Для действительно небольших отсортированных контейнеров это работает, но если размер контейнера превышает 1 000 000, он вылетает с кодом ошибки выше

Answer 1

Причина двоякая: во-первых, вы используете наихудшее из возможных значений разворота. Для уже отсортированных массивов требуется O (n ^ 2) времени выполнения. Обычно используемые стратегии состоят в том, чтобы использовать случайный элемент в качестве значения разворота, или среднего элемента, или медианы первого, последнего и среднего элемента.

Другая причина в том, что ваш стек переполнен из-за того, как вы делаете рекурсию. Чтобы избежать этого: найдите меньший диапазон и отсортируйте его рекурсивно. Затем отсортируйте больший диапазон, не используя рекурсию, а внутри той же функции, изменив параметр «first» и «last». Таким образом, глубина стека будет не более log n.

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