20-2-라.퀵 정렬
퀵 정렬(Quick Sort)은 이름 그대로 속도가 대단히 빠른 정렬 알고리즘이다. 큰 배열을 일정한 기준값을 경계로 하여 기준값보다 큰 값들과 작은 값들로 구성된 작은 두 개의 배열로 분할한다. 그리고 분할된 각 배열을 똑같은 방법으로 다시 정렬하는 점진적인 방법을 사용한다. 예제를 보자.
|
예 제 : QuickSort |
#include <Turboc.h>
#define SWAP(a,b) { int t;t=a;a=b;b=t; }
void QuickSort(char *ar, int num)
{
int left,right;
char key;
// 구간이 1이면 정렬 끝
if (num <= 1) return;
// 기준값 결정 : 배열상의 제일 끝 요소
key=ar[num-1];
for (left=0,right=num-2;;left++,right--) {
while (ar[left] < key) { left++; }
while (ar[right] > key) { right--; }
if (left >= right) break; // 좌우가 만나면 끝
SWAP(ar[left],ar[right]);
}
SWAP(ar[left],ar[num-1]); // 기준값과 i위치의 값 교환
QuickSort(ar,left); // 왼쪽 구간 정렬
QuickSort(ar+left+1,num-left-1); // 오른쪽 구간 정렬
}
void main()
{
char str[]="greathuman";
printf("정렬 전의 문자열 : %s\n",str);
QuickSort(str,strlen(str));
printf("정렬된 문자열 : %s\n",str);
}
"greatehuman"이라는 문자열을 퀵 정렬하면 "aaeghmnrtu"가 된다. 큰 배열을 분할하기 위해 먼저 기준값을 선정하는데 배열 선두나 마지막을 기준값으로 사용하는 것이 가장 쉽다. 그리고 for 루프에서 배열의 왼쪽과 오른쪽에 각각 left, right 포인터를 두고 중앙으로 이동하면서 left에 기준값보다 큰 값, right에 기준값보다 작은 값을 찾는다. 그리고 두 값을 교환하여 기준값보다 작은 값은 배열의 왼쪽으로 보내고 큰 값은 오른쪽으로 보낸다.
이 과정을 left와 right가 만날 때까지 반복하는데 이때 left 는 기준값보다 큰 값을 가리킨다. left와 기준값을 교환하여 left가 가리키는 값을 배열 끝으로 보내면 기준값의 왼쪽에는 이 값보다 작은 값만 있고 오른쪽에는 더 큰 값만 있을 것이다. 기준값이 있는 위치의 왼쪽 구간과 오른쪽 구간을 똑같은 방법으로 정렬하되 구간 크기가 1이 될 때까지 이 과정을 반복하면 전체 배열이 정렬된다. 그림으로 위 예제의 동작을 관찰해 보자.
이 예에서 기준값은 배열 제일 끝에 있는 n으로 선정되었다. left는 배열 선두에서부터 뒤쪽으로 이동하면서 n보다 더 큰 값을 찾고 right는 배열 끝에서부터 앞쪽으로 이동하면서 n보다 더 작은 값을 찾는다. for 문 안의 while루프가 이 검색을 수행하는데 이 예에서는 최초 left에 r이 검색되고 right에 a가 검색된다. 검색된 두 값을 교환하여 작은 값은 가급적 배열의 왼쪽으로 보내고 큰 값은 가급적 배열의 오른쪽으로 보낸다. 다음 루프에서 left와 right는 계속 중앙으로 이동하여 각각 t와 m을 찾아 두 값을 교환한다.
이 과정을 left가 right보다 더 작을 동안에 반복하는데 세 번째 단계에서 right가 h, left가 u를 가리킬 때 두 포인터는 이동을 중지한다. 그리고 기준값 n을 left 위치의 값(기준값보다는 더 크다)과 교환하면 기준값을 경계로 하여 왼쪽에는 n보다 더 작은 값만 남고 오른쪽에는 더 큰 값만 남게 된다. 이 상태를 만들면 왼쪽, 오른쪽 구간은 아직 정렬이 덜 되었지만 좌우 구간과 기준값 세 요소만 보면 정렬이 완료되었다.
남은 일은 좌우 구간을 개별적으로 다시 정렬하는 것인데 이 문제는 최초의 정렬 문제와 동일하므로 재귀 호출로 문제를 해결한다. 좌우 구간의 시작점과 길이를 적절히 계산해서 QuickSort 함수를 다시 호출한다. QuickSort 함수는 주어진 크기의 배열을 정렬하되 구간 길이가 1밖에 안될 때는 정렬이 이미 완료된 것으로 보고 곧바로 리턴한다. 그렇지 않다면 구간의 끝 값을 기준으로 다시 정렬하고 이 단계에서 생긴 또 다른 작은 구간들을 정렬하기 위해 재귀 호출이 발생할 것이다.
퀵 정렬의 성능은 기준값을 어떻게 설정하는가에 따라 결정되는데 기준값이 중간값에 가까울수록 좌우 구간이 균일하게 분할되어 더 빨리 정렬할 수 있다. 이 예제에서는 배열의 제일 끝값을 취했기 때문에 운에 따라 기준값이 결정되며 이미 정렬되어 있을 경우 항상 큰 값이 선택되어 왼쪽 구간만 커지는 문제가 있다. 그래서 기준값을 난수로 선택하여 한쪽으로 치우침을 방지하거나 아니면 적절한 중간값을 취하는 방법을 쓰기도 한다.
또 재귀 호출을 하기 때문에 배열이 아주 클 경우 스택 오버플로우가 발생할 위험이 있는데 이럴 때는 자체 스택을 만들어 비재귀하는 방식으로 개선할 수 있다. 아니면 구간이 아주 작을 때는 더 이상 재귀 호출을 하지 말고 선택 정렬이나 삽입 정렬같은 좀 더 간단한 알고리즘을 사용하는 방법도 흔히 사용된다. 그러나 요즘은 스택 크기가 아주 넉넉하기 때문에 굳이 비재귀 방식으로 바꿀 필요까지는 얺다.
퀵 소트는 다른 정렬 알고리즘에 비해 상대적으로 속도가 빠르고 큰 배열에 대해서도 잘 동작하기 때문에 가장 널리 사용되는 정렬 알고리즘이다. 그래서 C 표준 라이브러리는 퀵 소트 함수인 qsort 함수를 제공하는데 이 함수를 사용하면 임의의 배열에 대해 퀵 소트를 할 수 있다. 다음 예제는 똑같은 문자열을 표준 함수를 사용하여 퀵 소트한다.
|
예 제 : qsort |
#include <Turboc.h>
int compare(const void *a, const void *b)
{
if (*(char *)a == *(char *)b) return 0;
if (*(char *)a > *(char *)b) return 1;
return -1;
}
void main()
{
char str[]="greathuman";
printf("정렬 전의 문자열 : %s\n",str);
qsort(str,strlen(str),sizeof(char),compare);
QuickSort(str,strlen(str));
printf("정렬된 문자열 : %s\n",str);
}
출력 결과는 앞의 예와 동일하다. qsort는 퀵 소트 알고리즘대로 구간을 나누어 데이터를 교환하는데 단, 비교는 데이터 타입마다 다르므로 사용자가 직접 해야 한다. 비교하는 함수를 미리 만들어 두고 qsort 함수의 마지막 인수로 비교 함수의 포인터를 전달하면 된다. 표준 qsort 함수는 어셈블리로 고도로 최적화되어 작성되었지만 재귀 호출뿐만 아니라 비교를 위해 함수를 호출하기도 하므로 속도는 오히려 직접 만든 함수보다 더 느리다.
사실 이 함수만 사용할 수 있다면 정렬을 하는데는 별 불편함이 없을 것이다. 그러나 qsort가 아무리 임의의 타입에 대해서 잘 동작한다 하더라도 응용 프로그램의 특수성을 감안하면 이 함수로 모든 정렬을 다 할 수는 없다. 예를 들어 한글과 영문이 섞여 있는 문자열은 qsort 함수로 정렬할 수 없으며 직접 정렬 함수를 만들어 써야 한다.