퀵소트 - 알고리즘

 

Quick Sort

퀵 정렬(Quick Sort)는 호아(Hoare, 1962)가 정의한 알고리즘으로 이름에서도 알 수 있듯이 매우 빠른 수행속도를 가진다. 퀵 정렬은 합병정렬과 비슷하게 분할정복법(Divide-and-Conquer) 방법에 근거한다. 전체 데이터를 두 부분으로 분할한 다음, 분할된 각 부분은 재귀적으로 다시 퀵 정렬을 수행한다.

퀵 정렬은 합병정렬과 비슷하게 보이지만 합병정렬과는 다르게 전체 데이터를 균등하게 분할하는 것이 아니라 기준(pivot)을 선택하여 기준보다 작은 데이터를 왼쪽에 위치시키고, 큰 데이터는 오른쪽에 위치시킨다. 일반적으로 기준은 첫번째 데이터로 선택한다. 결과적으로 기준의 왼쪽에는 기준보다 작은 데이터가, 오른쪽에는 큰 데이터가 위치하게 된다.

기준에 따라 데이터의 이동을 살펴보면 다음과 같다.

15 22  13  27  12  10  20  25

1. 기준 아이템(15) 보다 작으면 왼쪽, 크면 오른쪽에 위치시켜 분할한다.

10  13  12  15  22  27  20  25

2. 부분배열을 정렬한다.

10  12  13  15  20  22  25  27

위 내용은 한번의 부분배열을 통해 정렬되는 과정을 보여준 것이다. 실제 퀵 정렬은 재귀적으로 더이상 분할할 수 없을때까지 분할된 후 정렬을 수행한다.

다음을 통해 좀 더 쉽게 퀵 정렬을 살펴볼 수 있다.

다음은 퀵 정렬에 대한 알고리즘이다.

void quicksort( index list[], index left, index right )
{
          if ( left < right ) {
                    index pivot = partition( list, left, right );
                    quicksort( list, left, pivot-1 );
                    quicksort( list, pivot+1, right);
          }
}

다음은 분할에 대한 알고리즘이다.

index partition( index list[], index left, index right)
{
          index pivot, temp, low, high;
          low = left;
          high = right+1;
          pivot = list[left];
          do {
                    do 
                              low++;
                    while ( list[low] < pivot );
                    do 
                              high--;
                    while ( list[high] > pivot );
                    if ( low < high ) SWAP( list[low], list[high], temp );
          } while ( low < high );
         
          SWAP( list[left], list[high], temp );
          return high;
}

그럼 이제 퀵 정렬의 복잡도를 살펴보자. 퀵 정렬은 최악의 경우 O(n²) 의 복잡도를 갖는다. 최악의 경우는 모든 데이터가 정렬된 경우이다. 이 경우 맨 앞의 데이터를 기준으로 선택했을 경우 데이터가 분할되지 못하므로 한번의 비교 연산이 n 번 이루어 진다고 하면 모든 데이터에 대해서는 O(n²)의 시간이 걸릴 것이다.

복잡도가 O(n²)인데 어떡해 이 알고리즘이 빠른 정렬이라고 불리게 되었을까? 그 이유는 평균의 경우 때문이다. 평균적인 경우 데이터에서 기준으로 선택될 확률은 모두 같다. 따라서, 평균은 모든 가능한 순서를 같은 횟수 정렬할 때의 평균 정렬시간이다. 말이 조금 어려울지 모르나 평균적인 경우에는 O(n log n)이 된다.

특히, O(n log n)의 복잡도를 가지는 다른 정렬알고리즘 보다도 더 빠르게 수행된다는 것이 증명되었다. 이러한 이유는 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만아니라, 한번 결정된 기준은 추후 연산에서 제외되는 성질을 가지기 때문이다.

퀵 정렬은 추가적인 메모리공간을 가지지 않는 제자리 정렬임에도 불구하고 한가지 단점은 앞서 말한대로 이미 정렬된 데이터에 대해서는 오히려 많은 시간이 걸리게 된다. 이러한 문제를 해결하는 방법은 기준을 선태할 때 왼쪽에서 선택하는 것이 아니라 중간 값을 기준으로 선택하는 것이다.


다음은 하나의 함수에 분할과 정렬을 모두 구현한 예이다.

void quicksort(int a[], int lo, int hi)
{
          //  lo is the lower index, hi is the upper index
          //  of the region of array a that is to be sorted
         int i=lo, j=hi, h;
         int x=a[(lo+hi)/2];

         //  partition
         do {    
             while (a[i]<x) i++;
             while (a[j]>x) j--;
             if (i<=j) {
                 h=a[i]; a[i]=a[j]; a[j]=h;
                 i++; j--;
             }
         } while (i<=j);

         //  recursion
         if (lo<j) quicksort(a, lo, j);
         if (i<hi) quicksort(a, i, hi);
}

퀵 정렬 라이브러리 함수 사용

---

보통 C언어 라이브러리에는 퀵 정렬 함수가 제공된다. 일반적으로 qsort 라는 이름으로 제공되며 다음과 같은 함수 원형을 가진다.

함수의 원형

void qsort(
          void *base,
          size_t num;
          size_t width,
          int (*compare) (const void *, const void *)
};

base - 배열의 시작주소
num - 배열 요소의 개수
width - 배열 요소 하나의 크기(바이트단위)
compare - 비교함수, 포인터를 통하여 두개의 요소를 비교하여 비교 결과를 정수로 반환, 사용자가 제공하여야 한다.

함수 사용 예

#include <stido.h>
#include <string.h>
#include <stdlib.h>

int compare( const void *arg1, const void *arg2 )
{
          if ( *(double) arg1  >  *(double *) arg2 ) return 1;
          else if ( *(double) arg1  ==  *(double *) arg2 ) return 0;
          else return -1;
}

int main()
{
          int i;
          double list[5] = { 2.1, 0.8, 2.2, 1.5, 3.3, 1.0 };
          qsort( (void *)list, (size_t)5, sizeof(double), compare );
         
          return 0;
}

Reference : Data Structures in C, 생능출판사
                 FOUNDATIONS of ALGORITHMS using C++ PSEUDOCODE, 사이텍미디어
                 http://ko.wikipedia.org/
                 http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm
출처 : http://proneer.tistory.com/entry/Sort-퀵-정렬Quick-Sort

2015_11_23 추가 (Integer 타입으로 테스트 코드)
(Visual Studio 에서 자동들여쓰기 정렬 기능 - Alt+F8 굿)

#include <stdio.h>

#include <stdlib.h>

void quicksort( int *a, int low, int high )

{

int pivot;

/* Termination condition! */

if ( high > low )

{

pivot = partition( a, low, high );

quicksort( a, low, pivot-1 );

quicksort( a, pivot+1, high );

}

}

void swap(int *a,int left,int right)

{

int temp;

temp = a[left];

a[left] = a[right];

a[right] = temp;

}

// pivot 위치를 left 즉, index의 첫번째 위치의 녀석으로 잡고 돌아간다..

int partition( int *a, int low, int high )

{

int left, right, pivot;

int *pivot_item = (int *)malloc(sizeof(int));

*pivot_item = a[low];

pivot = left = low;

right = high;

while ( left < right ) {

/* Move left while item < pivot */

while( a[left] <= *pivot_item ) left++;

/* Move right while item > pivot */

while( a[right] > *pivot_item ) right--;

if ( left < right ) swap(a,left,right);

}

/* right is final position for the pivot */

a[low] = a[right];

a[right] = *pivot_item;

return right;

}

void main()

{

int val[8] = {67, 90, 57, 25, 84, 32, 73, 54};

int i = 0;

quicksort(val, 0, 7);

printf("val : ");

for(i = 0; i < 8 ; i++)

{

printf("%d\n", val[i]);

}

}