Обнаружено переполнение стека при реализации рекурсивной сортировки Bubble.

Эй, я преобразовал этот код C # на с ++ как

void bubbleSort(int *inputArray, int passStartIndex, int currentIndex,int length)
{
if(passStartIndex == length - 1) return;
if(currentIndex == length - 1) return bubbleSort(inputArray, passStartIndex+1, passStartIndex+1,length);

//compare items at current index and current index + 1 and swap if required
int nextIndex = currentIndex + 1;
if(inputArray[currentIndex]>inputArray[nextIndex])
{
int temp = inputArray[nextIndex];
inputArray[nextIndex] = inputArray[currentIndex];
inputArray[currentIndex] = temp;
}

return bubbleSort(inputArray, passStartIndex, currentIndex + 1,length);
}

но когда я выполняю его на входном массиве, имеющем длину 50100, он показывает мне исключение

System.StackOverflowException было необработанным. Сообщение: необработанное.
исключение типа «System.StackOverflowException» произошло в example.exe

Что я делаю неправильно? Как это исправить?

2

Решение

«Что я делаю неправильно?»

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

Также посмотрите на: Ограничивает ли C ++ глубину рекурсии?


«Как это исправить?»

Самый простой способ избежать этой проблемы — никогда не создавать свой алгоритм как рекурсию. Но если у вас уже есть рекурсивное решение, подобное этому, в большинстве случаев его можно переписать в виде цикла или (что обычно намного проще): a хвостовая рекурсия.

По сути, если вы можете переписать свою функцию так, чтобы она никогда напрямую не передавала аргументы следующему вызову, вы выиграли. Если вы посмотрите на свою рекурсию, есть 2 места, где она звонит сама и до того, как звонок сделан, только currentIndex а также passStartIndex меняются. Представьте, что вы будете хранить эти индексы где-то в стороне, и текущий вызов функции будет просто сигнализировать «Я закончил, это те ценности, с которыми кто-то должен продолжать: … Теперь вы можете продолжать!», Это означает, что состояние, в котором находится функция, не нужно хранить. Тем самым вы получите Хвостовой вызов (особенно программа первого примера).

Вот полный пример того, как это можно сделать с вашим кодом: Шаг 1, Шаг 2

3

Другие решения

Это не решит вашу проблему (см. Предел рекурсии), но в алгоритме, который вы использовали, есть ошибка. Вы должны заменить

if (currentIndex == length - 1)
return bubbleSort(inputArray, passStartIndex+1, passStartIndex+1, length);

от

if (currentIndex == length - 1)
return bubbleSort(inputArray, passStartIndex+1, 0,length - 1);

Сортировка пузырьков должна перезапуститься до 0, потому что первый элемент находится не в нужном месте, а последний.

3

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector