бесконечный цикл — циклическое переполнение стека рекурсивной функции

Question

бесконечный цикл — циклическое переполнение стека рекурсивной функции

Я использую Qsort, основанный на employee.lastname,

left счетчик того, через сколько мы пробежали.

emptotal, (или же right) сколько всего есть.

Поскольку я знаю, что их 5, я установил точку поворота на 3. Моя проблема в том, что второй рекурсивный вызов во всем цикле повторяется, и я не могу понять, почему он повторяется. Он должен сосчитать (или вниз), а затем встретить его счетчик конца.

#include "./record.h"#include <string.h>
#include <algorithm>

void externalSort(EmployeeRecord employee[],int empcount,int emptotal)
{
int left=empcount,
right=emptotal;
EmployeeRecord pivot = employee[3];
while (left < right)
{
if (strcmp(employee[left].lastname, pivot.lastname) < 0 )
{
left++;
}
else if (strcmp(employee[right].lastname, pivot.lastname) < 0 )
{
right--;
}
else
{
std::swap(employee[left],employee[right]);
left++;
right--;
}
}

if (strcmp(employee[left].lastname, pivot.lastname) < 0 )
{
std::swap(employee[left],employee[empcount]);
left--;
}
if (strcmp(employee[right].lastname, pivot.lastname) < 0 )
{
std::swap(employee[right],employee[empcount]);
right++;
}

if (empcount < right) externalSort(employee,empcount,right);
if (left < emptotal) externalSort(employee,left,emptotal);
// The 2nd call is what seems to be looping, when I comment it out,
//the function doesn't loop.

}

0

c++infinite-loop qsort tail-recursion

Решение

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

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

if (strcmp(employee[left].lastname, pivot.lastname) < 0 )
{
left++;
}
else if (strcmp(employee[right].lastname, pivot.lastname) < 0 )
{
right--;
}

Я полагаю, что ваше левое утверждение верно, однако вы проверяете, меньше ли фамилия в правом индексе, чем стержень, когда вам, вероятно, следует проверить, больше ли оно. Часто такие мелочи дают неожиданный поток кода. Я не думаю, что это все исправит однако.

0

Источник

Accepted Answer

employee[3] выбирает четвертое, а не третье, независимо от того, сколько вещей нужно отсортировать.

Петля

while (left < right)

проверит элементы, которые вы сказали, чтобы проверить, но стержень не может быть в этом диапазоне.

После того, как вы решите, как с этим бороться, у вас есть еще три ошибки / вещи для размышления.

Вам нужно поменять местами в последней ветке?
Когда вы вернетесь, попробуйте externalSort (employee, empcount, pivot_index-1)
Аналогично для externalSort (employee, left, emptotal) необходимо использовать сводный индекс + 1

Существует некоторый относительно ясный псевдокод на Википедия. Вы предполагали, что можете использовать третью точку каждый раз. Там может быть меньше 3, когда вы повторяете.

1