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

5. 기준값으로 중윗값 사용

지금까지 결과를 보면, 그냥 가운데 값을 기준값으로 해서 구현한 것이 제일 빠른 것으로 보인다. (인덱스 2개를 사용하고, 재귀 호출 사용하고, 난수 사용하지 않고)

그런데, 아주 특수한 데이터에 대해서는, 고정으로 가운데 값을 잡았을 때, O(n2)의 나쁜 성능이 나올 수도 있을 것이다. (가운데 값으로 잡히는 값이, 계속해서 최솟값 혹은 최댓값인 데이터)

이에 대한 대안으로, 난수를 이용해서 가운데 값을 계속해서 교환해가면서 정렬하는 것도 생각해볼 수 있으나 난수 생성에 의한 약간의 속도 저하를 감내해야 한다.

 

이보다 좀 더 좋은 방법은 중앙값을 잡고, 이 중앙값을 맨 가운데 위치에 넣고 정렬을 수행하는 것이다.

/**
사용 인덱스 개수: 2개(양방향 증가)
재귀/스택 이용  : 재귀
스택구현 방법   : N/A
pivot 결정      : (s,m,e)에서 중윗값을 pivot으로 하고 가운데 위치시킴
*/
void quickSort_recur_median(vector<int> &v, int s, int e){      
  if(s>=e) return;  

  int m = (s+e)/2;
  if(v[s] > v[m]) swap(v[s],v[m]);
  if(v[m] > v[e]) swap(v[m], v[e]);
  if(v[s] > v[m]) swap(v[s], v[m]);

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

위 코드에서 보듯이, 가장 왼편/중앙/오른 편의 3개의 수 중에서 중윗값을 찾고, 이 중윗값을 v[m]에 위치하게 해서 정렬을 수행해 나간다.

 

가장 왼쪽에 있는 v[s] 값과, 가운데에 있는 v[m] 값, 그리고 가장 오른 편에 있는 v[e] 값을 정렬해서, v[s] <= v[m] <= v[e]가 된 상태에서 정렬을 수행하는 방법이다.

이렇게 3개의 값을 정렬하는 데 2번의 비교와 최대 2번의 교환으로 가능하고, 이렇게 가장 왼편에 있는 수와 가운데 수 그리고 가장 오른 편에 있는 수가 정렬된 상태에서 정렬이 시작되고, 정렬하는 방법으로 가장 중앙에 위치한 값을 기준값으로 정해서 파티션을 나누고 정렬해 나가기에, 재귀 호출해가는 횟수를 꽤나 줄일 수 있어서 효율적인 방법이다.

 

아래 표에서와 같이 수행 시간을 비교해 보면, 이처럼 중윗값을 이용한 정렬이, 난수를 이용한 방법보다 빠르며, 그냥 중간값을 이용한 방법과 유사한 속도를 내는 것을 알 수 있다.

 

DataType/Algorithm	stlSort	quickSort_recur_center	quickSort_recur_randomCenter	quickSort_recur_median
ordered	1120	512	1129	550
reversed	1960	1019	1245	1088
same	2000	1133	1194	1105
randomized	2116	1290	1455	1373