루핑 재귀 함수 C++

Question

employee.lastname을 기반으로 Qsort를 사용하고 있습니다.
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) 

당신이 확인을 말한 항목을 검사하지만 피벗 그 범위하지 않을 수 있습니다.

당신이 어떻게 대처할 지 결정한 후에는 생각할 3 가지 더 많은 실수가 있습니다.

1. 마지막 분기를 바꿔야합니까? 당신이 재귀 때
2. , 당신은 몇 가지가 피벗 인덱스 + 1

를 사용해야합니다 (왼쪽 직원, emptotal)에 externalSort에 대한 유사

externalSort (직원, empcount, pivot_index-1) 시도 상대적으로 명확한 코드는 Wikipedia에 있습니다. 매번 세 번째 포인트를 사용할 수 있다고 가정했습니다. 재발 할 때 3 점 미만일 수 있습니다.

Answer 2

내가 할 첫 번째 일은 strcmp 문이 실제로 수행해야한다고 생각하는 것을 확인하는 것입니다.

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

내가 오른쪽 인덱스의 마지막 이름이 큰 경우 당신은 아마 확인해야 피벗,보다 작은 경우 그러나 당신이 확인되어, 왼쪽 문이 올바른 생각합니다. 때때로 이런 작은 것들은 예기치 않은 코드 흐름을 줄 것입니다. 나는 이것이 모든 것을 고칠 것이라고 생각하지 않는다.