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

3. 난수(Random)를 이용한 기준값(pivot) 선정 방법

바로 위에서 봤듯이, 기준값을 정할 때 난수를 이용하면 특수한 데이터에 대해서 기준값을 고정했을 때 발생하는 속도 저하 문제를 해결할 수 있다.

 

그러나, 이때 난수 생성을 위해 소모되는 약간의 속도 저하를 감수해야 한다.

아래 표는 가운데 값을 기준점으로 해서 구현한 것과, 난수를 이용해서 가운데 값을 변화시켜가면서 구현한 코드의 정렬 시간 비교이다. (500만 개 값에 대한 정렬)
그냥 가운데 값을 기준점으로 정했을 때가, 난수를 사용한 경우보다 좀 더 빠름을 알 수 있다.

 

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

 

소스는 아래와 같다.

int getRand(int s, int e){
  int high=rand();
  int low=rand();
  int r = (high << 16) | low;   

  return s + (r % (e-s+1));  
}

/**
사용 인덱스 개수: 2개(양방향 증가)
재귀/스택 이용  : 재귀
스택구현 방법   : N/A
pivot 결정      : 가운데 값
*/
void quickSort_recur_center(vector<int> &v, int s, int e){      
  if(s>=e) return;

  int pivot = v[(s+e)/2];  
  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_center(v,s,j);  quickSort_recur_center(v,i,e); 
}
void quickSort_recur_center(vector<int> &v){
  quickSort_recur_center(v,0,v.size()-1);    
}

/**
사용 인덱스 개수: 2개(양방향 증가)
재귀/스택 이용  : 재귀
스택구현 방법   : N/A
pivot 결정      : random선택 후 가운데 위치한 값과 교체
기타            : 함수 진입단에 수행조건 없음. 대신 재귀호출에 대한 조건 있음
*/
void quickSort_recur_randomCenter(vector<int> &v, int s, int e){
  //int p = s + rand()%(e-s+1); //[s,e] 사이 난수
  int p = getRand(s,e);
  int m = (s+e)/2;    
  swap(v[p],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;
    }              
  };        

  if(j > s) quickSort_recur_randomCenter(v,s,j);
  if(i < e) quickSort_recur_randomCenter(v,i,e);  
}
void quickSort_recur_randomCenter(vector<int> &v){
  quickSort_recur_randomCenter(v,0,v.size()-1);    
}

위 코드에서 주의할 점은 난수를 생성함에 있어 그대로 rand()를 사용한 것이 아니라, getRand()라는 별도의 함수를 만든 것이다. rand()에 의해서는 0~32767까지의 수만 얻어낼 수 있기에, 이보다 더 많은 수에 대해 정렬하고자 할 때는, 그냥 rand()를 사용해서는 필요한 임의의 위치를 정할 수 없기 때문이다. (만약 그대로 rand를 사용해서 코딩하게 되면, 특수한 데이터에 대해서 매우 안 좋은 성능을 보인다.)

getRand의 구현은 여러 가지 방법이 있겠으나, 여기서는 두 번 rand를 사용해서 난수 생성 후, 그 두 개의 난수를 상위 16비트와 하위 16비트에 배치시켜, 32비트의 난수가 발생되도록 하였다.

int high=rand();
int low=rand();
int r = (high << 16) | low;