Looping Рекурсивная функция C++

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. 

} 

Answer 1

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

Петля

while (left < right) 

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

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

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

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

Answer 2

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

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

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