[C언어 알고리즘] 정렬(6) - 퀵정렬 (Quick Sort)

퀵정렬(Quick Sort)은 분할-정복(Divide and Conquer)전략을 사용하는 알고리즘으로 1960년 C.A.R Hoare에 의해 처음 고안되어 가장 널리 알려진 정렬 방법 중 하나입니다. 퀵정렬은 아주 빠른 속도를 낼 뿐 아니라 원리도 간단해서 많은 부분에서 응용되고 있습니다.

빛처럼 빠른 정렬??

퀵정렬은 연속적인 분할(Partition)에 의해 정렬을 합니다. 여기서 분할은 축(Pivot)을 중심으로 왼쪽은 이 값보다 작은 값 오른쪽은 큰 값으로 배열한다는 의미입니다. 이렇게 축을 기준으로 분할된 왼쪽 오른쪽 부분을 다시 분할하여 분할된 크기가 1이 될 때까지 반복하여 정렬합니다.

 

퀵정렬의 의사코드를 보면 다음과 같습니다.

퀵정렬 (a, N)
1. N > 1 이면
   1.1. N크기의 배열을 분할 (Partition)하여 축(Pivot)값의 위치를 mid로 넘긴다.
   1.2. 퀵정렬 (a, mid)
   1.3. 퀵정렬 (a+mid_+1, N-mid-1)

위 내용을 보면 mid를 기준으로 왼쪽과 오른쪽 부분배열에 대한 퀵정렬을 재귀적으로 다시 수행한다는 의미로 받아들이면 됩니다.

 

초기 데이터가 아래와 같을 때, 

l

e

a

r

n

a

l

g

o

r

i

t

h

m

축(Pivot)값을 배열의 맨 마지막 값인 'm'으로 잡고 배열의 왼쪽부터는 'm'보다 큰 값을 배열의 오른쪽 부터는 'm'보다 작은 값을 찾아 교환합니다. 왼쪽과 오른쪽 값을 찾는 인덱스가 만날 때까지 진행을 하는데 아래에서는 두 번의 값을 교환하고 왼쪽에서 찾는 값은 'o'이고 오른쪽에서 찾는 값은 'g'이고 인덱스가 만나서 지났으므로 'o'와 축 (Pivot)을 교환합니다. 

 

l

e

a

h

n

a

l

g

o

r

i

t

r

m

 

l

e

a

h

i

a

l

g

o

r

n

t

r

m

 

l

e

a

h

i

a

l

g

m

r

n

t

r

o

이제는 이전 축의 값인 'm'을 기준으로 왼쪽 부분 배열과 오른쪽 부분 배열에 대한 퀵정렬을 재귀적으로 수행합니다.

 

왼쪽 부분배열을 보면 'g'를 축으로 퀵정렬을 수행합니다. 마찬가지로 왼쪽에서는 'g'보다 큰 값을 오른 쪽에서는 'g'보다 작은 값을 찾아 교환합니다. 그리고 왼쪽과 오른쪽 인덱스가 만날 경우 축( pivot)값을 교환합니다.  그러면 왼쪽의 부분배열은 'a', 'e', 'a'가 되겠네요.

l

e

a

h

i

a

l

g

 

a

e

a

h

i

l

l

g

 

a

e

a

g

i

l

l

h

이런 식으로 부분배열의 크기가 1보다 작아질 때까지 수행합니다.

 

C언어로 작성한 소스코드는 다음과 같습니다.

#include <stdio.h>
#include <string.h>

void print_data(char a[], int n);
char data[] = "learnalgorithm";

void quick_sort(char a[], int n)
{
    char v, t;
    int i, j;
    int i1, j1;
    if (n > 1) {
        v = a[n-1];
        i1 = i = -1;
        j1 = j = n -1;

        while (i < j) {
            while (a[++i] < v)
                ;
            while (a[--j] > v)
                ;
            if (i < j) {
                printf("정렬 범위: %d~%d,피봇-[%c],Left(%c)-Right(%c) 교환 전,", i1+1, j1-1, a[n-1], a[i], a[j]);
                print_data(a, n);
                t = a[i];
                a[i] = a[j];
                a[j] = t;
                printf("정렬 범위: %d~%d,피봇-[%c] 교환 후,", i1+1, j1-1, a[n-1]);
                print_data(a, n);
            }

        }
        //print_data(data, strlen(data));
        printf("정렬 범위: %d~%d,기존 피봇-[%c], 값-[%c] 교환 전,", i1+1, j1-1, a[n-1], a[i]);
        print_data(a, n);
        t = a[i];
        a[i] = a[n-1];
        a[n-1] = t;
        printf("정렬 범위: %d~%d,기존 피봇-[%c] 교환 후,", i1+1, j1-1, a[i]);
        print_data(a, n);
        quick_sort (a, i);
        quick_sort (a+i+1, n-i-1);
    }
}

void print_data(char a[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf ("%c ", a[i]);
    }
    printf ("\n");
}

void main (int argc, char *argv[])
{
    /* char data[] = "learnalgorithm"; */
    print_data(data, strlen(data));
    printf ("=====================\n");
    printf ("==== 퀵정렬 시작 =====\n");
    printf ("=====================\n");
    quick_sort(data, strlen(data));
    printf ("=====================\n");
    printf ("==== 퀵정렬 종료 =====\n");
    printf ("=====================\n");
    print_data(data, strlen(data));

}

실행 결과는 아래와 같습니다.

PS C:\CS> ./quick_sort.exe
l e a r n a l g o r i t h m 
=====================
==== 퀵정렬 시작 =====
=====================
정렬 범위: 0~12,피봇-[m],Left(r)-Right(h) 교환 전,l e a r n a l g o r i t h m
정렬 범위: 0~12,피봇-[m] 교환 후,l e a h n a l g o r i t r m 
정렬 범위: 0~12,피봇-[m],Left(n)-Right(i) 교환 전,l e a h n a l g o r i t r m 
정렬 범위: 0~12,피봇-[m] 교환 후,l e a h i a l g o r n t r m 
정렬 범위: 0~12,기존 피봇-[m], 값-[o] 교환 전,l e a h i a l g o r n t r m
정렬 범위: 0~12,기존 피봇-[m] 교환 후,l e a h i a l g m r n t r o 
정렬 범위: 0~6,피봇-[g],Left(l)-Right(a) 교환 전,l e a h i a l g
정렬 범위: 0~6,피봇-[g] 교환 후,a e a h i l l g
정렬 범위: 0~6,기존 피봇-[g], 값-[h] 교환 전,a e a h i l l g
정렬 범위: 0~6,기존 피봇-[g] 교환 후,a e a g i l l h
정렬 범위: 0~1,기존 피봇-[a], 값-[a] 교환 전,a e a
정렬 범위: 0~1,기존 피봇-[a] 교환 후,a e a
정렬 범위: 0~0,기존 피봇-[a], 값-[e] 교환 전,e a
정렬 범위: 0~0,기존 피봇-[a] 교환 후,a e
정렬 범위: 0~2,기존 피봇-[h], 값-[i] 교환 전,i l l h
정렬 범위: 0~2,기존 피봇-[h] 교환 후,h l l i
정렬 범위: 0~1,기존 피봇-[i], 값-[l] 교환 전,l l i
정렬 범위: 0~1,기존 피봇-[i] 교환 후,i l l
정렬 범위: 0~0,기존 피봇-[l], 값-[l] 교환 전,l l
정렬 범위: 0~0,기존 피봇-[l] 교환 후,l l
정렬 범위: 0~3,피봇-[o],Left(r)-Right(n) 교환 전,r n t r o
정렬 범위: 0~3,피봇-[o] 교환 후,n r t r o
정렬 범위: 0~3,기존 피봇-[o], 값-[r] 교환 전,n r t r o
정렬 범위: 0~3,기존 피봇-[o] 교환 후,n o t r r
정렬 범위: 0~1,피봇-[r],Left(t)-Right(r) 교환 전,t r r
정렬 범위: 0~1,피봇-[r] 교환 후,r t r
정렬 범위: 0~1,기존 피봇-[r], 값-[t] 교환 전,r t r
정렬 범위: 0~1,기존 피봇-[r] 교환 후,r r t
=====================
==== 퀵정렬 종료 =====
=====================
a a e g h i l l m n o r r t

일반적으로 퀵정렬은 분할이 거의 정확하게 절반이 되는 경우 가장 좋은 성능을 냅니다.

그런데 보통 퀵정렬의 구현은 재귀적 호출로 구현되어 있기 때문에 예전에는 정렬할 데이터가 많은 경우 빈번한 재귀 호출로 내부 스택의 크기가 커져 프로그램이 뻗어버리는 경우도 있었습니다. 관련 내용은 테스트 후 추가 포스팅하겠습니다.