퀵소트 함수, 재귀와 노재귀(Non-Recursive) 형태,,, 동적배열 스택 이용

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

  // 좌우 인덱스 설정 및 비교, 교환
  left=0; right=n-2;
  while(TRUE){
   while(arr[left] < pv) ++left;
   while(right && arr[right] > pv) --right; // 시작 인덱스보다 작거나 같으면 값 조사 필요 없다.
   if(left >= right) break;
   t=arr[left]; arr[left]=arr[right]; arr[right]=t;
   ++left; --right;
  }
 
  // 피벗 자리와 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
 }
}




// 동적 배열 스택 이용
// (연결리스트로 스택을 구성하면 그때그때 메모리 할당에 상당 시간을 잡아먹으므로 배보다 배꼽이 크다.)
void __stdcall QuickSortNoRecur(char *arr, int n)
{
 int start, end, left, right;
 char 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(TRUE){
    while(arr[left] < pv) ++left;
    while(right>start && arr[right] > pv) --right; // 시작 인덱스보다 작거나 같으면 값 조사 필요 없다.
    if(left >= right) break;
    t=arr[left]; arr[left]=arr[right]; arr[right]=t;
    ++left; --right;
   }
   
   // 피벗 자리와 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);
}