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

퀵 정렬은 다른 정렬 방법보다 속도에 대한 가변성이 높다. 기본 아이디어는 어떤 값을 기준으로 해서 partition으로 나눈 후, 나눈 것에 대해서 계속 정렬해가는 것인데, 기준값 어떻게 잡느냐에 따라 수행 속도 차이가 많이 나고, 재귀 호출을 사용하는지 스택을 사용하는지에 따라서도 속도와 메모리 사용량이 달라진다.

 

이번 챕터에서는 이러한 여러 가지 사항들을 고려해가며 퀵 정렬을 구현해보고 서로 속도 비교를 해볼 것이다.

 

1) 인덱스 1개 이용한 구현
2) 기준점 위치 (오른 편? 중앙?)
3) 난수(Random)를 이용한 기준값(pivot) 선정 방법
4). 기준값으로 중윗값 사용

 

---

1. 인덱스 1개 이용한 구현

 

앞에서 소개한 퀵 정렬에 대한 소스 코드는, 모두 2개의 인덱스를 사용한 알고리즘을 구현한 것이다. 즉, 왼편에서 i가 오른 편으로 이동하고, 오른 편에서 j가 왼편으로 이동하면서 정렬해 나간다.

 

인덱스 1개를 사용해서 간편하게 퀵 정렬을 구현하는 방법이 있다.

 

기본 알고리즘은 다음과 같다.

quickSort(v,s,e)  //v 데이터의 start부터 end까지를 정렬

1. if(s<e)인 경우만 실행
2. p=s  //p: 기준점인 pivot이 들어갈 자리
3. i를 [s,e)까지 증가시키면서
   3.1 if(v[i]<=v[e])이면 swap(v[p],v[i])하고 ++p
4. swap(v[p], v[e]) //기준점을 i위치로 이동
5. 왼쪽편에 대해 정렬: quickSort(v,s,p-1)
6. 오른편에 대해 정렬: quickSort(v,p+1,e) 

초기에 기준값을 데이터의 가장 끝 값으로 했고, 나중에 이 값이 기준점이 되는 지점인 p에 들어가게 된다. 따라서, 초기에 p를 s에 위치시켜놓고, 데이터의 값을 하나씩 기준값과 비교하면서 작은 값들이 나오면 p의 위치를 하나씩 증가시키는 것이다. (위 Flow에서 3.1)

 

위와 같이 했을 때 기준값을 중심으로 왼쪽에는 작은 값들이, 오른쪽에는 큰 값들이 어째서 되는지 궁금할 수 있는데, 아래 예제를 차분히 보면 이해될 수 있을 것이다.

 

 

구현한 소스 코드는 다음과 같다.

/**
사용 인덱스 개수: 1개(일방향 증가)
재귀/스택 이용  : 재귀
스택구현 방법   : N/A
pivot 결정      : 가장 오른쪽 값
*/
void quickSort_one_recur_right(vector<int> &v, int s, int e){    
  if(s>=e) return;

  int p=s;
  for(int i=s;i<e;++i) if(v[i]<=v[e]) swap(v[p++],v[i]);

  swap(v[p], v[e]);        
  quickSort_one_recur_right(v,s,p-1); quickSort_one_recur_right(v,p+1,e);     
}

코드가 꽤나 간단하다.
이 코드는 기준점(pivot)을 맨 오른쪽 값으로 했다. 이렇게 고정했을 경우는, 데이터가 난수의 경우는 괜찮으나, 데이터가 이미 정렬되어 있거나(ordered), 역으로 정렬되어 있거나(reversed), 데이터의 값이 전부 같은 경우(same)에 매우 안 좋은 성능을 보인다.

 

이를 개선하기 위해 임의의 난수 값을 찾고, 그 임의의 값을 기준점인 가장 오른쪽 값과 교환 후 정렬을 시도하게 해볼 수 있다. 아래가 그 코드이다.

/**
사용 인덱스 개수: 1개(일방향 증가)
재귀/스택 이용  : 재귀
스택구현 방법   : N/A
pivot 결정      : random으로 결정 후, 가장 오른쪽 후미값과 교체
*/
void quickSort_one_recur_randomRight(vector<int> &v, int s, int e){  
  if(s>=e) return;

  int p = s + rand()%(e-s+1); //[s,e] 사이 난수          
  swap(v[p],v[e]);
  p=s;
  for(int i=s;i<e;++i) if(v[i]<=v[e]) swap(v[p++],v[i]);

  swap(v[p], v[e]);        
  quickSort_one_recur_randomRight(v,s,p-1); quickSort_one_recur_randomRight(v,p+1,e);  
}

이렇게 하면 이미 정렬된 데이터에 대해서는 성능이 개선되지만, 역으로 정렬된 경우(reversed)와 모든 데이터가 똑같은 값의 경우에는 여전히 성능이 안 좋다.

[표] 만 개 값에 대한 정렬 시간. 단위: ms

DataType/Algorithm	stlSort	quickSort_one_recur_right	quickSort_one_recur_randomRight
ordered	2	570	2
reversed	2	804	797
same	3	827	799
randomized	3	2	3

 

한 개 인덱스를 이용해서 퀵 정렬을 구현한 경우는, 데이터가 일반적인 난수의 경우는 속도가 괜찮으나, 특수한 데이터(역으로 정렬되어 있거나, 같은 값이 많은 경우)에 대해서는 속도가 매우 안 좋다. 따라서, 앞 챕터에서 다룬 것처럼, 2개의 인덱스를 가지고 퀵 정렬에 대한 구현을 하는 것이 맞겠다.

 

아래는 인덱스 1개를 가지고 여러 가지 방법으로 퀵 정렬을 구현해본 것으로, 어떻게 하든 reversed 데이터와 same 데이터에 대한 속도 저하를 막을 수 없다.

/**
사용 인덱스 개수: 1개(일방향 증가)
재귀/스택 이용  : 스택
스택구현 방법   : stl:stack<pair<int,int>>
pivot 결정      : random->v[e] (random선택 후 가장 후미값과 교체)
*/
void quickSort_one_stackPair_randomRight(vector<int> &v, int s, int e) {
  srand((unsigned int)time(0));
  stack<pair<int,int>> st;  
  st.push(make_pair(s,e));  
  while (!st.empty()) {      
    pair<int,int> tmp = st.top(); st.pop();
    int ss = tmp.first;    
    int ee = tmp.second;

    if (ss < ee) {
      int p = ss + rand() % (ee - ss + 1);
      swap(v[p], v[ee]);
      p = ss;
      for (int i = ss; i < ee; ++i) if (v[i] <= v[ee]) swap(v[p++], v[i]);
      swap(v[p], v[ee]);

      st.push(make_pair(p+1,ee)); //right
      st.push(make_pair(ss,p-1)); //left     
    }    
  }
}
void quickSort_one_stackPair_randomRight(vector<int> &v){
  quickSort_one_stackPair_randomRight(v,0,v.size()-1);    
}

/**
사용 인덱스 개수: 1개(일방향 증가)
재귀/스택 이용  : 스택
스택구현 방법   : vector<int>
pivot 결정      : random->v[e](random선택 후 가장 후미값과 교체)
*/
void quickSort_one_stackInt_randomRight(vector<int> &v, int s, int e) {
  srand((unsigned int)time(0));
  vector<int> st((e-s+2)*2);  
  int top = 0;

  //e부터 넣는것에 주의
  st[++top] = e; st[++top] = s;  
  while (top > 0) {
    int ss = st[top--]; 
    int ee = st[top--];    

    if (ss < ee) {
      int p = ss + rand() % (ee - ss + 1);
      swap(v[p], v[ee]);
      p = ss;
      for (int i = ss; i < ee; ++i) if (v[i] <= v[ee]) swap(v[p++], v[i]);
      swap(v[p], v[ee]);

      st[++top] = ee; st[++top] = p+1;
      st[++top] = p-1; st[++top] = ss;      
    }    
  }
}
void quickSort_one_stackInt_randomRight(vector<int> &v){
  quickSort_one_stackInt_randomRight(v,0,v.size()-1);    
}

/**
사용 인덱스 개수: 1개(일방향 증가)
재귀/스택 이용  : 스택
스택구현 방법   : vector<pair<int,int>>
pivot 결정      : random선택 후 가장 후미값과 교체
*/
void quickSort_one_stackVectorPair_randomRight(vector<int> &v, int s, int e) {
  srand((unsigned int)time(0));
  vector<pair<int, int>> st(e - s + 2);
  int top = 0;

  st[++top] = make_pair(s, e);
  while (top > 0) {
    pair<int, int> tmp = st[top--];
    if (tmp.first < tmp.second) {
      int p = tmp.first + rand() % (tmp.second - tmp.first + 1);
      swap(v[p], v[tmp.second]);
      p = tmp.first;
      for (int i = tmp.first; i < tmp.second; ++i) if (v[i] <= v[tmp.second]) swap(v[p++], v[i]);
      swap(v[p], v[tmp.second]);

      st[++top] = make_pair(p + 1, tmp.second);
      st[++top] = make_pair(tmp.first, p - 1);
    }    
  }
}
void quickSort_one_stackVectorPair_randomRight(vector<int> &v){
  quickSort_one_stackVectorPair_randomRight(v,0,v.size()-1);    
}

/**
사용 인덱스 개수: 1개(일방향 증가)
재귀/스택 이용  : 재귀
스택구현 방법   : N/A
pivot 결정      : (s,m,e)에서 중윗값을 pivot으로 하고 가운데 위치시킴
*/
void quickSort_one_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 p=s;
  for(int i=s;i<e;++i) if(v[i]<=v[e]) swap(v[p++],v[i]);

  swap(v[p], v[e]);        
  quickSort_one_recur_median(v,s,p-1); quickSort_one_recur_median(v,p+1,e);   
}
void quickSort_one_recur_median(vector<int> &v){
  quickSort_one_recur_median(v,0,v.size()-1);    
}

 

[표]1개 인덱스를 사용한 퀵 정렬을 이용해서 만 개 값에 대해 정렬할 때 소요되는 시간 [ms]

DataType/Algorithm	stlSort	quickSort_one_recur_right	quickSort_one_recur_randomRight	quickSort_one_recur_median	quickSort_one_stackPair_randomRight	quickSort_one_stackVectorPair_randomRight
ordered	2	570	2	3	3	2
reversed	2	804	797	806	795	805
same	3	827	799	798	806	827
randomized	3	2	3	3	4	3