기존 퀵소트 코드의 문제점 수정 및.... 중복 비교 제거

아래는 기존 퀵소트 핵심 코드 중의 일부분이다.
while(TRUE){
while(arr[left] < pv) ++left;
while(arr[right] > pv) --right; //<<<<<<<<<<  이 부분 문제
if(left >= right) break;
t=arr[left]; arr[left]=arr[right]; arr[right]=t;
++left; --right;
}
이재규 알고리즘 책이나 김상형 혼연C 퀵정렬 부분, 기타 웹에서 돌아다니는 많은 소스들이 이런 형태인데 조금 문제가 있다.
위 부분에서 right를 left와 비교하지 않으면,
right가 left보다 작거나 같은 상태임에도 계속 right값 감소시키면서 값을 비교하고,,,
더구나 작은 값을 못 찾은 경우는 0, -1까지 계속 진행되어 버린다.

이를테면 {0,1,3,4,2}와 같은 형태인 경우를 생각해보면...
피봇값은 마지막 2이고 첫문장에 의해 left는 값3의 위치에 가 있는 상태이고
이 경우 그 다음 right 루프문은 값3이 있는 위치까지 도달하면 거기의 값을 비교할 필요도 없이 바로 탈출하면 되지만,,,,,
위와 같은 코딩에서는 left, right  비교문이 없으므로 지혼자서 불필요하게 계속 돌아
1값 있는데까지 가서 값이 피봇보다 작은지 확인하고 그제서야 멈춘다.

unsinged형 자료 정렬시는 더 심각한 문제가 발생할 수 있다고 본다.
{5, 4, 3 ,2, 1} 등의 역순배열일 경우 이 경우 right는 이동하면서 1보다 작은 값을 찾게 되는데  해당 배열에서는 없으므로
계속 -1, -2, -3,,,,,좌측으로 가는 데 할당되지 않는 메모리는 보통 0xcc로 채워지므로 4바이트면 양수 0xcccccccc값을 가진다.
 이것은 무조건 1보다 크므로 위의 코딩이라면 계속 좌로 이동할 것으로 보인다.(테스트는 안해봤다...)

right가 left보다 작거나 같으면 위 문제부분 루프문에서 배열값을 확인할 필요도 없고, 더 이상 루프를 돌 필요도 없다.
왜 이렇게 쉽게 보이는 부분을 그냥 방치했는지 모르겠다.

그러므로 left와 right 비교하는 코드가 필요한다.
while(arr[right] > pv) --right; //<<<<<<<<<<  이 부분을  우선
while(left < right && arr[right] > pv) --right;
이런 식으로 수정할 수 있다. 그런데 바로 아래 문장인 if(left >= right) break; 과
중복되어 효율적인 코드가 못 된다.
중복비교는 웹 검색해서 퀵 소트 찾아보는 중 아주 많은 코드들이 이를 방치하고 있었다...;;;

이 문제를 좀 생각해 본 끝에 goto문을 사용하니 해결이 되긴 되었다.
물론 플래그 변수 같은 것을 두어 탈출할 수도 있으나 변수 선언과 값 입력시간의 낭비가 있어 별로라고 본다.
goto문을 사용해 단숨에 루프 2개를 탈출하는 구조를 취하면 된다. 다른 더 좋은 방법이 있으면 알려주시길 바랍니다.

아래는 위의 문제 코드를 고친 형태이다...모양은 썩 좋진 않은 것 같다.ㅡㅡ;
while(1){
   while(arr[left]<pv) ++left;
   while(1){
    // 2단계 건너뛰어야 하므로 goto 사용,,, 따로 변수 설정해서 처리가능하지만 더 느릴 것이다.
    if(left>=right) goto outside;
    if(arr[right]>pv){--right;}
    else{break;}
   }
   t=arr[left]; arr[left]=arr[right]; arr[right]=t;
   ++left; --right;
  }

 outside:

 ~~~~~~~~~~
 



// 재귀함수
template <typename T> void __stdcall QuickSort(T *arr, int n)
{
 int left, right;
 T pv, t;
 
 // 갯수가 2 이상이면
 if(n > 1){
 
  // 피벗 결정
  pv=arr[n-1];

  // 좌우 인덱스 설정 및 비교, 교환
  left=0; right=n-2;

  while(1){
   while(arr[left]<pv) ++left;
   while(1){
    // 2단계 건너뛰어야 하므로 goto 사용,,, 따로 변수 설정해서 처리가능하지만 더 느릴 것이다.
    if(left>=right) goto outside;
    if(arr[right]>pv){--right;}
    else{break;}
   }
   t=arr[left]; arr[left]=arr[right]; arr[right]=t;
   ++left; --right;
  }

 outside:
 
  // 피벗 자리와 left 자리 교환
  arr[n-1]=arr[left]; arr[left]=pv;

  // 좌우측 재귀호출
  QuickSort(arr, left);    // (left-1)-0+1
  QuickSort(arr+left+1, n-left-1); // (n-1)-(left+1)+1
 }
}

// 동적 배열 스택 노재귀 함수
// (연결리스트로 스택을 구성하면 그때그때 메모리 할당에 상당 시간을 잡아먹으므로 배보다 배꼽이 크다.)
template <typename T> void __stdcall QuickSortNoRecur(T *arr, int n)
{
 int start, end, left, right;
 T pv, t;
 int *pBase;
 int top=-1;

 // 인덱스를 저장할 스택 할당: 최대 스택의 크기 2n+2 <--- 역순정렬시 최대 스택 필요
 pBase=(int*)malloc(sizeof(int)*(2*n+2));
 if(!pBase){
  MessageBoxW(NULL, L"스택 할당 에러", L"QuickSortNoRecur 에러", MB_TOPMOST|MB_ICONERROR);
  return;
 }

 // 첫번째 요소 push: 먼저 꺼내려는 것을 나중에 push해야 한다.(LIFO 구조)
 pBase[++top]=n-1;
 pBase[++top]=0;

 // 스택이 empty 상태면 빠져나온다.
 while(top != -1){
  // pop
  start=pBase[top--]; // pop
  end=pBase[top--]; // pop

  // 갯수가 2 이상인 경우
  if(end-start+1 > 1){

   // 피벗 결정
   pv=arr[end];

   // 좌우측 인덱스 설정 및 비교, 교환
   left=start; right=end-1;
   while(1){
    while(arr[left]<pv) ++left;
    while(1){
     // 2단계 건너뛰어야 하므로 goto 사용,,, 따로 변수 설정해서 처리가능하지만 더 느릴 것이다.
     if(left>=right) goto outside;
     if(arr[right]>pv){--right;}
     else{break;}
    }
    t=arr[left]; arr[left]=arr[right]; arr[right]=t;
    ++left; --right;
   }

  outside:

   // 피벗 자리와 left 자리 교환
   arr[end]=arr[left]; arr[left]=pv;

   // 좌우측 push: 먼저 꺼내려는 것을 나중에 push해야 한다.(LIFO 구조)
   pBase[++top]=end;   // push(end);
   pBase[++top]=left+1;  // push(left+1);
   pBase[++top]=left-1;  // push(left-1);
   pBase[++top]=start;   // push(start);  
  }
 }

 // 스택 해제
 free(pBase);
}