[정렬알고리즘] Quick Sort 퀵소트

 Quick Sort 는 내가 가장 자주 이용하는 정렬알고리즘이다. 구현도 비교적 쉽고, 아주 매우 빠르다! 물론, 퀵소트보다 빠른 알고리즘은 존재한다. 이것에 대해서는 나중에 다시 다루기로하겠지만 기본적으로 퀵소트를 응용한 알고리즘이다. 퀵소트 알고리즘은 정렬알고리즘이지만, k번째로 큰(작은)요소를 검색하는 알고리즘에도 응용 할 수있다. k번째 크거나 작은 요소의 검색을 구현하려고 할 때, 요소를 모두 정렬한 상태에서 k번째 요소를 읽는 방법보다 더 나은 방법이 존재한다.
 그럼 바로 Quick Sort 의 소스 코드를 살펴보자.

void QuickSort(int Array[], int p, int q) { if( p < q ){ int t = Partition(Array, p, q); QuickSort(Array, p, t-1); QuickSort(Array, t+1, q); } }
  소스코드에서도 알 수 있는것처럼, 퀵소트는 분할정복기법과 매우 비슷하다. 분할정복은 해결하고자 하는 문제를 부분문제로 잘게 나눈 후, 부분문제의 해를 조합해서 전체문제의 해를 구하는 기법이다. 퀵소트의 경우 부분해를 재조합할 필요가 없다. 위의 퀵소트 소스코드에서는 배열 Array 로 주어진 수열의 p번째 요소에서 q번째 요소까지 정렬한다. p번째 요소와 q번째 요소사이의 인덱스를 하나 정하여 부분수열의 정렬을 수행하게 함으로써 수열이 정렬된다. 
  퀵소트의 핵심은 Partition 함수이다. 입력수열의 몇 번째 요소를 기준으로 하여 두 부분수열로 나눌것인가를 결정하는 Partition 함수는 아래와 같다.

int Partition(int Array[], int p, int q) { int base = Array[q]; int i = p-1, j; for(j=p; j<q; ++j){ if(Array[j] < base){ ++i; swap(&Array, i, j); } } ++i; swap(&Array, i, q); return i; }

  Partition 함수를 뜯어보자.

1. 먼저, 수열의 맨 끝요소( Array[q] )를 기준값으로 설정한다.
2. 인덱스 i 는 p-1 로 초기화하고, 인덱스 j 를 입력수열의 첫번째요소부터 맨끝요소를 제외한 요소를 모두 순회하도록 한다.
3. 만약, Array[j]값이 기준값보다 작다면 i값을 증가시키고 Array[i]와 Array[j]를 교환한다.
4. 순회가 끝난 시점에 인덱스 i 의 값을 1 증가 시킨다. 증가된 인덱스 i 보다 작은 인덱스의 요소값은 기준값보다 작은값으로 채워지게 된다. 반면, 인덱스 i  보다 큰 인덱스의 요소값은 기준값보다 크거나 같은 값들로 채워진다. 즉, 인덱스 i 가 가리키는 지점이 기준값으로 하여 입력수열이 분리되는 지점이 된다.
5. 마지막으로 인덱스 i 가 가리키는 요소값과 기준값( 맨 끝요소인 Array[q] )을 교환하고, 경계지점인 i 를 리턴한다.

 위에서 예로든 Partition 함수의 소스코드에서는 기준값을 입력수열의 맨 끝요소로 지정하고 있지만, 특별한 이유가 있어서 맨 끝요소로 하고 있는것은 아니다. 이 기준값을 어떻게 설정하는가는 매우 중요하다. 이 기준값에 의해서 입력수열이 두 부분수열로 나누어지고 있다는 것을 상기하자. 가능한한 나누어지는 두 부분수열의 길이가 비슷하도록 분할하는것이 중요하다. 예를들어 입력수열의 길이가 10 인데, 두 부분수열의 길이가 각각 1 과 9 로 나뉘어 지는것은 바람직하지 않다. 따라서, 부분수열의 길이가 균등하게 분할되게끔 기준값을 어떻게 설정할 것인가하는 문제는 중요하다. 좋은 성능을 내게끔 기준값을 정하는 한 가지 방법은 입력수열의 요소중 아무값이나 랜덤하게 정하는 것이다. 이 방법은 평균적으로 매우 좋은 성능을 나타내는것으로 알려져있다. 랜덤하게 기준값을 정하는것이 불합리해 보이지만, 최적의 계산량에 아주 근접한 계산량으로 정렬이 가능한 점과, 구현이 매우 간단한 덕분에 자주 사용하는 편이다.
 퀵소트는 정렬하고자 하는 수열의 요소수가 n일 때, 일반적으로 O(n*log(n)) 의 시간복잡도를 갖는다. 최악의 경우는 O(n*n) 이다. 퀵소트의 성능은 위에서도 언급했듯이 기준값을 어떻게 설정하는가에 따라서 크게 달라질 수 있다. 기준값을 수열의 랜덤한 요소로 설정하는 방법을 사용하는 경우 거의 항상 최적의 성능으로 정렬을 수행할 수 있다. 정렬하고자하는 수열의 크기가 크면 클수록 최악의 성능이 나타날 확률이 작아짐이 알려져있다. 따라서, 퀵소트의 성능은 거의 항상 O(n*log(n)) 의 시간복잡도를 갖는다.
 
 어느정도 부분수열의 길이가 짧아지는 경우 퀵소트를 재귀호출하는 방법대신에 삽입정렬을 호출하여 정렬해버리는 응용도 가능하다. 짧은 수열의 경우 삽입정렬이 빠르게 작동하기 때문이다. 삽입정렬은 O(n*n)으로 긴 수열의 정렬에는 매우 느리게 작동하지만 짧은 수열의 정렬에는 매우 빠르게 작동한다. 계산량을 오더표기법으로 표기할 때 생략되는 상수항이 작기 때문이다.

 Quick Sort 를 응용하여, k번째 큰 요소를 검색하는 함수 QuickSearch 함수를 살펴보자.

int QuickSearch(int Array[], int p, int q, int k) { if(p < q){ int t = Partition(Array, p, q); if(t == k) return Array[t]; else if(t > k) QuickSearch(Array, p, t-1, k); else QuickSearch(Array, t+1, q, k); } }
 Partition 함수는 그대로 이용한다. 분할경계 인덱스와 검색하고자하는 인덱스를 비교하여 어느 한쪽만 재귀호출하고 있다는 점에 주목해주길 바란다. 기준값을 경계로 하여 큰값과 작은 값들이 나뉘어진 상태에서 검색하고자 하는 인덱스가 경계인덱스보다 큰지 작은지 비교하여 어느 한 쪽만 재귀적으로 검색해 나가고 있다.

 만약, 요소수가 n개인 수열을 정렬한 뒤 k번째 요소를 검색하는 전략을 사용한다면, 수열에서 k 번째로 큰 요소값을 검색하는 방법의 계산량은 정렬알고리즘의 계산량만큼 걸리게 되지만, Quick Sort 의 응용버전인 QuickSearch 함수를 이용하면, O(n) 으로 검색을 수행할 수 있다.