007. [부록]여러 가지 퀵 정렬(Quick Sort) 구현 방법(4)

4. 스택을 사용한 비 재귀판 퀵 정렬 구현

너무 많은 재귀 호출에 의해 스택 오버플로가 염려될 때는, 재귀를 사용하지 않는 비 재귀형 퀵 정렬의 구현을 생각할 수 있다. 자체 스택을 가지고 구현된다.

아래 코드는 중앙을 기준값(pivot)으로 하는 코드를 스택을 이용하여 재귀 호출 없이 구현한 코드이다.

/**
사용 인덱스 개수: 2개(양방향 증가)
재귀/스택 이용  : 스택
스택구현 방법   : vector<int>
pivot 결정      : 중앙값
*/
void quickSort_stack_vectorInt_center(vector<int> &v, int s, int e){      
  vector<int> st((e-s+2)*2);
  int top = 0;

  st[++top] = e; st[++top] = s; 
  while (top > 0) {
    int ss = st[top--]; 
    int ee = st[top--];      

    if (ss < ee) {  
      int m = (ss+ee)/2;

      int pivot = v[m];    
      int i=ss, j=ee;
      while(i<=j){
        while(v[i] < pivot) ++i;
        while(v[j] > pivot) --j;
        if(i<=j) {
          swap(v[i],v[j]);
          ++i; --j;
        }              
      };    
      if(i < ee) { st[++top] = ee; st[++top] = i;}
      if(ss < j){ st[++top] = j; st[++top] = ss;}      
    }
  }    
}
void quickSort_stack_vectorInt_center(vector<int> &v){
  quickSort_stack_vectorInt_center(v,0,v.size()-1);    
}

스택의 구현은, C++ 기본 라이브러리에서 제공하는 stack 클래스를 사용할 수도 있으나, 배열 혹은 vector를 이용해서 경량의 스택을 만들 수 있기에, 여기서는 vector를 사용해서 구현했다.(stack 클래스를 사용하는 것보다 속도가 더 빠르다.)

스택에 들어가는 것은 데이터의 처음 위치를 나타내는 s와, 마지막을 나타내는 e이다. 재귀 호출을 할 때 이 두 값이 인자로 사용되어 호출되기에, 그것을 대신하기 위해 그 2개의 값을 스택에 저장해서 pop 하면서 사용하는 것이다.

 

스택은 LIFO(Last In First Out)이기에 - 제일 마지막에 넣은 게 가장 먼저 나옴- , s와 e를 스택에 넣을 때, e를 먼저 넣고 그다음에 s 값을 넣는 것에 유의한다. 그래야 s가 나오고 그다음에 e를 꺼낼 수 있다.

재귀 호출을 사용한 버전과 속도 비교를 해보면, 오히려 미세하게 시간이 더 걸림을 볼 수 있다.
자체적으로 스택 메모리를 생성하고 관리하는데 걸리는 오버헤드가, 재귀 호출에 의한 오버헤드보다 더 큰 모양이다. (50만 개 값에 대한 정렬 시간. 단위 ms)

 

DataType/Algorithm	stlSort	quickSort_recur_center	quickSort_stack_vectorInt_center
ordered	1120	512	565
reversed	1960	1019	1103
same	2000	1133	1110
randomized	2116	1290	1364