퀵 정렬은 '분할 정복(Divide and Conquer)'이라는 방식을 사용한 정렬 알고리즘.
분할 정복이란, 전체를 구성하는 구성요소들을 잘게 나누어 정복하는 방식을 말한다.
퀵 정렬의 과정
1. 데이터 집합에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소는 순서에 관계없이 기준 요소의 왼쪽에, 큰 요소는 오른쪽에 위치 시킨다.
2. 나눈 데이터 집합을 다시 1번의 과정을 거치게 한다.
3. 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻게 된다.
다음의 그림은 3, 1, 4, 8, 5, 2, 9, 6, 7 순으로 되어있는 데이터 집합을 퀵 정렬로 정렬한 것이다.
먼저 첫번째 요소인 3을 기준 값으로 선택하고,
3보다 작은 요소는 왼쪽으로 큰 요소는 오른쪽으로 분할한다.
다음 기준 값으로 1을 정하고 분할한다.
2를 기준 값으로 분할
4를 기준 값으로 분할
8을 기준 값으로 분할
5를 기준 값으로 분할
6을 기준 값으로 분할
7을 기준 값으로 분할
9를 기준 값으로 분할
정렬 완료
※기준 요소 선택
퀵 정렬은 기준 요소 선택에 따른 성능 차이는 보인다.
이를 보완하기 위해서는 데이터 집합의 처음 세 개의 요소 중 중간값을 기준요소를 정하여 분할하는 방법이 있다.
위의 퀵 정렬 과정은 배열을 사용하기에는 많은 수행과정이 필요하므로 부적절하다.
배열을 사용한 퀵 정렬을 위해서는 왼쪽과 오른쪽 끝에서 각각 요소를 검사하여 왼쪽은 기준 요소보다 큰 요소를 오른쪽에서는 기준 요소보다 작은 요소를 찾아 서로 바꾸는(swap) 방식을 사용하면 가능하다.
다음 그림에서는 5, 1, 6, 4, 8, 3, 7, 9, 2 순서로 되어 있는 데이터 집합을 정렬하는 예이다.
왼쪽에서는 기준 요소보다 큰 요소를 찾고먼저 첫번째 요소인 5를 기준으로 하여
오른쪽에서는 기준 요소보다 작은 요소를 찾아 서로 바꾼다.
이러한 과정을 반복한 뒤
기준 요소와 왼쪽에서 부터 올라온 마지막 요소와 바꾸어 준다.
위의 과정을 반복하게 된다면 정렬이 가능하게 된다.
퀵 정렬 소스 코드
#include <stdio.h>
void Swap( int* A, int* B )
{
int Temp = *A;
*A = *B;
*B = Temp;
}
int Partition( int DataSet[], int Left, int Right )
{
int First = Left;
int Pivot = DataSet[First];
++Left;
while( Left <= Right )
{
while( DataSet[Left] <= Pivot && Left < Right ) //데이터 집합의 왼쪽부터 검색
++Left;
while( DataSet[Right] >= Pivot && Left <= Right ) //데이터 집합의 오른쪽 부터 검색
--Right;
if ( Left < Right )
Swap( &DataSet[Left], &DataSet[Right]);
else
break;
}
Swap( &DataSet[First], &DataSet[Right] );
return Right;
}
void QuickSort(int DataSet[], int Left, int Right)
{
if ( Left < Right )
{
int Index = Partition(DataSet, Left, Right);
QuickSort( DataSet, Left, Index - 1 ); //기준요소를 기준으로 왼쪽 데이터 집합 정렬
QuickSort( DataSet, Index + 1, Right ); // 기준요소를 기준으로 오른쪽 데이터 집합 정렬
}
}
int main( void )
{
int DataSet[] = {6, 4, 2, 3, 1, 5};
int Length = sizeof DataSet / sizeof DataSet[0];
int i = 0;
QuickSort( DataSet, 0, Length-1 );
for ( i=0; i<Length; i++ )
{
printf("%d ", DataSet[i]);
}
printf("\n");
return 0;
}
C 표준 라이브러리 퀵 정렬 함수(qsort() 함수)
void qsort (
void *base, // 데이터 집합 배열의 주소
size_t num, // 데이터 요소의 개수
size_t width, // 한 데이터 요소의 크기
int (__cdecl * compare) (const void *, const void*) //비교 함수에 대한 포인터
);
비교 함수의 원형
int compare( (void *) & elem1, (void *) & elem2 );
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
/* 리턴값이
< 0 이면, _elem1이 _elem2보다 작다.
0 이면, _elem1이 _elem2와 같다.
> 0 이면, _elem1이 _elem2보다 크다. */
int CompareScore( const void *_elem1, const void *_elem2 )
{
int* elem1 = (int*)_elem1;
int* elem2 = (int*)_elem2;
if ( *elem1 > *elem2)
return 1;
else if ( *elem1 < *elem2)
return -1;
else
return 0;
}
int main( void )
{
int DataSet[] = {6, 4, 2, 3, 1, 5};
int Length = sizeof DataSet / sizeof DataSet[0];
int i = 0;
qsort((void*)DataSet, Length, sizeof (int), CompareScore );
for ( i=0; i<Length; i++ )
{
printf("%d ", DataSet[i]);
}
printf("\n");
return 0;
}
