4. 퀵 정렬
퀵 정렬은 C.A.R. Hoare가 만든(The Computer Journal, 5:10-15, 1962.) 가장 우수한 편에 속하는 평균 수행능력을 갖는 정렬 방식이다. (단, 조건에 따라서는 분포수 정렬, 역사상 정렬, 래딕스 정렬방법이 빠르다.)버블정렬이나 선택정렬의 경우, 바로 옆의 데이터를 서로 비교하여 교환하는 방식인데, 이러한 방식은 데이터가 최종으로 정렬될 위치에서 멀면 멀수록 비효율적이라고 할 수 있다.
퀵 정렬은 멀리 떨어진 데이터를 서로 교환함으로써 이러한 비효율성을 개선하였다. 간단히 설명하면, 'Pivot' 이라 불리는 임의의 값을 설정한 후에 배열의 양끝방향에서부터 탐색을 시작해서 Pivot값보다 큰 값과 작은값을 발견하여 서로 치환하는 방식이다.
단점으로는, Pivot 값이 같은 것끼리의 순서관계가 파괴된다. 이러한 것이 매우 중요한 데이터의 경우 퀵소트를 쓰지 않는 것이 바람직하다.
예제를 보면서 수행과정을 자세히 알아보도록 하자.
다음과 같은 값들이 입력되었다고 하자.
|
입력값 : |
26 |
5 |
37 |
1 |
61 |
11 |
59 |
15 |
48 |
19 |
|
Step 1 : |
26 |
5 |
19 |
1 |
61 |
11 |
59 |
15 |
48 |
37 |
|
↑ |
↑ |
↑ |
여기에서는 Pivot값을 맨 왼쪽 값으로 정한다고 가정한다.(임의의 키값 혹은 맨 오른쪽의 값이어도 상관없다.) 따라서 처음 Pivot값은 '26'이 된다. 다음엔 맨 왼쪽에서 오른쪽으로 가면서 Pivot값보다 큰값을 찾고(3번째값인 '37'이 되겠다.), 맨오른쪽에서 왼쪽으로 가면서 Pivot값보다 작은값(10번째 인 '19'가 되겠다.)을 찾아 바꾼다.
|
Step 2 : |
26 |
5 |
19 |
1 |
15 |
11 |
59 |
61 |
48 |
37 |
|
↑ |
↑ |
↑ |
왼쪽포인터와 오른쪽포인터가 위치한 곳에서부터 시작하여 계속해서 왼쪽포인터는 오른쪽으로 가면서 Pivot값보다 큰값을, 오른쪽포인터는 왼쪽으로 가면서 Pivot값보다 작은값을 찾는다. 따라서 이번엔 '61'과 '15'을 찾아 바꾸게 된다.
|
Pass 1 : |
11 |
5 |
19 |
1 |
15 |
26 |
59 |
61 |
48 |
37 |
|
|
|
|
|
|
|
↑ |
|
|
|
|
마찬가지로 반복하면 이번엔 왼쪽포인터는 '59'를 오른쪽 포인터는 '11'을 가리키게 된다. 이렇게 왼쪽포인터와 오른쪽포인터가 엇갈리게되면 마지막에 찾은가장 작은값과 Pivot값을 바꾼다. 즉 '11'과 '26'을 바꾼다.
|
Step 1 : |
[ 11 |
5 |
1 |
19 |
15 ] |
26 |
[ 59 |
61 |
48 |
37 ] |
|
|
↑ |
|
↑ |
↑ |
|
|
|
|
|
|
이렇게 마치고나면, Pivot값을 중심으로 왼쪽에는 Pivot값보다 작은 값들이, 오른쪽에는 Pivot값보다 큰 값들이 놓여지게 된다. 이것이 Quick Sort의 한 단계이다. 이번엔 위의 과정을 Pivot값의 오른쪽에 위치한 레코드들에 대해서 반복한다. 즉, 처음 Pivot값은 맨처음의 '11'이 되고, 맨왼쪽에서 Pivot값인 '11'보다 큰값인 '19'와 맨오른쪽에서 Pivot값보다 작은 값인 '1'을 찾아 바꾼다.
|
Pass 2 : |
[ 1 |
5 ] |
11 |
[19 |
15 ] |
26 |
[ 59 |
61 |
48 |
37 ] |
|
|
|
|
↑ |
|
|
|
|
|
|
|
다음에는 왼쪽포인터와 오른쪽포인터가 엇갈리게되므로, 그 다음에 찾은 가장 작은 값인 '1'와 Pivot값인 '11'을 바꾼다.
이를 계속해서 반복한 결과는 다음과 같다.
|
Pass 3 : |
1 |
5 |
11 |
[19 |
15 ] |
26 |
[ 59 |
61 |
48 |
37 ] |
|
|
|
|
|
|
|
|
|
|
|
|
|
Pass 4 : |
1 |
5 |
11 |
15 |
19 |
26 |
[ 59 |
61 |
48 |
37 ] |
|
|
|
|
|
|
|
|
|
|
|
|
|
Pass 5 : |
1 |
5 |
11 |
15 |
19 |
26 |
[ 48 |
37] |
59 |
[61] |
|
|
|
|
|
|
|
|
|
|
|
|
|
Pass 6 : |
1 |
5 |
11 |
15 |
19 |
26 |
37 |
48 |
59 |
[61] |
|
|
|
|
|
|
|
|
|
|
|
|
|
Pass 7 : |
1 |
5 |
11 |
15 |
19 |
26 |
37 |
48 |
59 |
61 |
1. 키(Pivot)값을 선택한다. 2. 레코드의 왼쪽에서부터 오른쪽으로 Pivot값보다 큰값을 찾는다. 3. 레코드의 오른쪽에서부터 왼쪽으로 Pivot값보다 작은값을 찾는다. 4. 2,3에 의해 찾은 값을 서로 바꾼다. 5. 2,3의 포인터가 교차할때까지 반복한다. 6. 포인터가 교차할 경우, 오른쪽포인터가 찾은 값과 Pivot값을 교환한다. 7. 앞의 순서를 반복한다.
퀵 정렬의 Pivot값은 배열의 가장 처음값이나 끝값등 마음대로 설정할 수 있으나, 가장 좋은 것은 배열안에 있는 모든 값의 평균값이다. 평균값이 Pivot이 되면 첫 Pass에서 평균값보다 큰 배열, 그리고 작은 배열이 반반씩 균등하게 나뉘어지므로 최고의 효율을 낼 수 있다. 너무 크거나 작은 값이 Pivot으로 선정되면 최악의 경우 한쪽 배열에 한 개, 또 한쪽 배열에 나머지 부분이 들어갈 수도 있다. 이때는 자기 호출의 깊이가 n정도가 되며 실행 시간이 n2에 비례하는 정도로 떨어진다.
퀵 정렬의 Pivot값은 보통 배열의 처음값, 혹은 끝의 값을 취하지만 한번의 탐색을 통해 평균을 내어 그 평균과 가장 가까운 값을 Pivot값으로 설정하게 만들면 효율을 높일 수 있다. 그런데 최적의 Pivot값을 찾을 때 오히려 최악의 Pivot값이 선정되어 Sort를 진행할 경우보다 더 많은 비용이 들 수도 있으므로 이러한 구현을 추가할 때는 상황을 보아 신중하게 결정해야 하겠다.
퀵 정렬은 무작위한 배열을 정렬하는데는 매우 빠르지만 구간이 넓을 경우에 한하고 구간이 어느정도 좁혀지면 그다지 빠르지 않으므로 적당한 점까지 퀵 정렬을 한 후, 다음은 삽입정렬로 대체한다. 삽입정렬은 대충 정렬한 데이터를 다시 정렬할 때 진가를 발휘한다.
퀵 정렬은 재귀호출판과 비재귀호출판이 있는데 둘 다 잘 쓰인다. 그런데 비재귀 호출판을 쓸 수 있으면 비재귀 호출판을 쓰는 것이 더 낫다. 왜냐하면 재귀호출판은 데이터가 매우 커질 경우 Stack Overflow가 날 수 있기 때문이다.
알고리즘
QuickSort(a[], l, r)
// 배열 a[]의 부분 배열 a[l : r]을 오름차순으로 정렬
if (r > l) then {
i ← partition(a[], l, r); // i는 파티션이 끝난 뒤에 사용된 피봇의 인덱스
QuickSort(a[], l, i-1);
QuickSort(a[], i+1, r);
}
end QuickSort()
partition(a[], l, r)
// 가장 오른쪽 원소 a[r]을 피봇으로 하여 a[]를 분할
v ← a[r]; // 가장 오른쪽 원소를 피봇으로 정함
i ← l-1; // 왼쪽에서 오른쪽으로 움직이는 포인터
j ← r; // 오른쪽에서 왼쪽으로 움직이는 포인터
for ( ; ; ) do {
do { i ← i+1; } while (a[i] < v); // 피봇 값보다 작으면 i 값 증가
do { j ← j-1; } while (a[j] > v); // 피봇 값보다 크면 j 값 감소
if (i ≥ j) then break; // 왼쪽과 오른쪽 포인터가 교차하면 중지
temp ← a[i]; a[i] ← a[j]; a[j] ← temp; // a[i]와 a[j] 교환
}
temp ← a[i]; a[i] ← a[r]; a[r] ← temp; // a[i]와 a[r] 교환
return i;
end partition()
void Quicksort(int l, int r)
{
int i,j,v;
if(r>l)
{
v=buf[r]; i=l-1; j=r;
while(1)
{
while(buf[++i]<v);
while(buf[--j]>v);
if(i>=j) break;
swap(i,j);
}
swap( i, r);
Quicksort( l, i-1);
Quicksort( i+1, r);
}
}
u 최선의 경우
Ø CN = 2CN/2 + N
Ø CN » N logN
u 평균
Ø CN » 2N lnN
u 평균 비교 회수는 최선의 경우에 비해 약 38% 정도 많아지므로 큰 차이가 나지 않는다고 할 수 있음
Ø 2N lnN » 1.38 N logN
u 스택을 사용하여 순환을 제거
u 작은 부분화일의 경우 삽입 정렬 사용
u 중간값 분할(Median-of-Three Partitioning)
순환 제거
void QuickSort(int a[], int l, int r)
{
int i, j, v;
Stack sf(50);
for ( ; ; ) {
while (r > l) {
i = partition(a, l, r);
if (i-l > r-i) {
sf.push(l); sf.push(i-1); l = i+1;
}
else {
sf.push(i+1); sf.push(r); r = i-1;
}
if (sf.empty()) break;
r = sf.pop(); l = sf.pop();
}
}
작은 부분 파일
u 부분화일의 크기가 일정 크기 이하로 작아지면 삽입 정렬 수행
u “if (Right > Left)”
Ø “if (Right - Left <= M) InsertionSort(Left, Right)”
u M : 5 ~ 25
u 많은 응용에서 약 20% 정도의 시간 절감 효과가 있음
void QuickSort(int a[], int l, int r)
{
int i, j, v;
if (r-l <= M) InsertionSort(a, l, r);
else {
v = a[r]; i = l-1; j = r;
for ( ; ; ) {
while (a[++i] < v);
while (a[--j] > v);
if (i >= j) break;
swap(a, i, j);
}
swap(a, i, r);
QuickSort(a, l, i-1);
QuickSort(a, i+1, r);
}
}
중간값 분할
u 분할 원소를 선택할 때 왼쪽, 가운데, 오른쪽 원소 중 값이 중간인 원소를 선택
u 왼쪽, 가운데, 오른쪽 원소를 정렬한 후 가장 작은 값을 a[l], 가장 큰 값을 a[r], 중간 값을 a[r-1]에 넣고, a[l+1], …, a[r-2]에 대해 분할 알고리즘을 수행
u 장점
Ø 최악의 경우가 발생하는 확률을 낮추어 줌
Ø 경계 키(sentinel key)를 사용할 필요가 없음
Ø 전체 수행 시간을 약 5% 감소시킴
void QuickSort(int a[], int l, int r)
{
int i, j, m, v;
if (r - l > 1) {
m = (l + r) / 2;
if (a[l] > a[m]) swap(a, l, m);
if (a[l] > a[r]) swap(a, l, r);
if (a[m] > a[r]) swap(a, m, r);
swap(a, m, r-1);
v = a[r-1]; i = l; j = r-1;
for ( ; ; ) {
while (a[++i] < v);
while (a[--j] > v);
if (i >= j) break;
swap(a, i, j);
}
swap(a, i, r-1);
QuickSort(a, l, i-1);
QuickSort(a, i+1, r);
}
else if (a[l] > a[r]) swap(a, l, r);
}
