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

2. 기준점 위치 (오른 편? 중앙?)

위에서 1개 인덱스를 사용했을 때, 코딩은 간단해지나, 특수한 데이터에 대해 속도가 안 좋아짐을 살펴봤다. 따라서 인덱스 2개를 사용한 방법이 정석이라 할 수 있는데, 인덱스 2개를 사용할 때 기준값을 어디로 정하느냐도 생각해볼 만한 문제이다.

알고리즘 책에서 일반적으로 소개하는 기준값(pivot) 위치는 맨 오른쪽이다. 이렇게 구현한 코드는 아래와 같다.

/**
사용 인덱스 개수: 2개(양방향 증가)
재귀/스택 이용  : 재귀
스택구현 방법   : N/A
pivot 결정      : 후미값
*/
void quickSort_recur_right(vector<int> &v, int s, int e){  
  int p; //p:기준점이 들어갈 자리 
  if(s < e){        
    int i=s-1,j=e;
    while(true){
      while(v[++i] < v[e]);
      while((--j >= s) && (v[j] > v[e]));
      if(i >= j) break;      
      swap(v[i],v[j]);      
    };          
    swap(v[i], v[e]);    
    quickSort_recur_right(v,s,i-1); quickSort_recur_right(v,i+1,e); 
  }  
}
void quickSort_recur_right(vector<int> &v){
  quickSort_recur_right(v,0,v.size()-1);    
}

이렇게 했을 때 문제는, 이미 정렬되어 있는 데이터에 대해서 O(n2) 정도로, 매우 안 좋은 성능을 보이는 것이다. 이를 해결하기 위해서는, 임의 위치의 값을 맨 오른쪽 값과 교환한 후, 그 오른쪽 값을 pivot 값으로 해서 정렬하는 것을 반복하면 된다.

/**
사용 인덱스 개수: 2개(양방향 증가)
재귀/스택 이용  : 재귀
스택구현 방법   : N/A
pivot 결정      : random선택 후 가장 후미값과 교체
*/
void quickSort_recur_randomRight(vector<int> &v, int s, int e){  
  int p; //p:기준점이 들어갈 자리 
  if(s < e){    
    p = s + rand()%(e-s+1); //[s,e] 사이 난수          
    swap(v[p],v[e]);

    int i=s-1,j=e;
    while(true){
      while(v[++i] < v[e]);
      while((--j >= s) && (v[j] > v[e]));
      if(i >= j) break;      
      swap(v[i],v[j]);      
    };          
    swap(v[i], v[e]);    
    quickSort_recur_randomRight(v,s,i-1); quickSort_recur_randomRight(v,i+1,e); 
  }  
}
void quickSort_recur_randomRight(vector<int> &v){
  quickSort_recur_randomRight(v,0,v.size()-1);    
}

[표] 만 개 데이터에 대한 정렬 시간 [ms]

DataType/Algorithm	stlSort	quickSort_recur_right	quickSort_recur_randomRight
ordered	2	323	2
reversed	2	2	1
same	3	1	1
randomized	3	2	3