퀵 정렬 알고리즘은 재귀적인 방법으로 문제를 해결하는 알고리즘입니다.
퀵 정렬 알고리즘은 피벗 값을 선택하여 피벗 값보다 작은 값들은 왼쪽으로 보내고 큰 값들은 오른쪽으로 보낸 후에 이들 사이에 피벗을 위치시키는 원리를 이용합니다. 이후 피벗보다 작은 값들을 재귀 호출로 정렬하고 피벗보다 큰 값들도 재귀 호출로 정렬하는 방식입니다.
그런데 퀵 정렬은 어떠한 요소를 피벗으로 선택하냐에 따라 성능에 차이가 납니다. 만약 전체 요소의 중간 순위의 요소를 선택하면 재귀 호출에서 반씩 나누어 정렬을 하게 되어 좋은 성능을 발휘합니다. 하지만 가장 작은 값이나 가장 큰 값을 피벗으로 선택하면 최악의 성능을 발휘합니다.
여기에서는 맨 앞과 맨 뒤, 그리고 중간 위치의 요소를 비교하에 세 값 중에 중간 값을 피벗으로 선택할게요.
알고리즘
퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리)
조건(n<=1)
종료
피벗을 선택한다.
피벗과 맨 앞의 요소를 교환한다.
big:=0
small:=n
반복(big<small)
반복(big:=big+1; big<n; big:=big+1)
조건(compare(base[0],base[big])<0)
루프 탈출
반복(small:small-1;small>0;small:small-1)
조건(compare(base[0],base[small])>0)
루프 탈출
조건(big<small)
교환(base [big], base [small])
교환(base [0], base [small])
퀵 정렬(base,small, compare)
퀵 정렬(base+big, n-big, compare)
퀵 정렬 알고리즘의 탈출 조건은 n이 1보다 작거나 같을 때입니다.
점근식 계산
n 개의 원소인 배열을 정렬할 때 걸리는 수행 시간을 T(n)이라고 합시다. 퀵 정렬은 재귀적인 방법으로 해결하고 반 씩 나누어 재귀 호출이 이루어지는데 재귀 호출이 진행하기 전에 비교에 걸리는 시간을 S(n)이라고 합시다. 그리고 n 개인 원소를 재귀 호출 전에 비교하는 횟수는 n번이므로 S(n)=n입니다.
T(n) = 2*T(n/2) + n = n^2T(n/n^2) + 2*n = … = h*n
재귀는 원소 개수가 1보다 작으면 탈출하므로 n^h =1 일 때 더 이상 재귀 호출은 발생하지 않습니다.
h = logn이므로 T(n) = nlogn
그런데 이처럼 퀵 정렬에서 재귀 호출 시에 절반으로 나누어지는 것은 피벗을 잘 선택하였을 때입니다. 따라서 퀵 정렬의 수행 시간은 ω(nlogn)이라고 말할 수 있습니다. n이 충분히 크면 퀵 정렬의 평균 수행 시간도 위처럼 동작하여 Θ(nlogn)입니다.
최악은 매 번 분할 시 피벗이 제일 큰 값이거나 제일 작은 값일 때 발생합니다. 만약 피벗이 제일 큰 값이면 피벗보다 작은 값들이 있는 부분만 재귀 함수가 동작합니다. 따라서 T(n)은 다음과 같습니다.
T(n) = T(n-1) + n = T(n-2) + n + n-1 = T(n-3) +n + n-2 + n-1 = …
이처럼 분할하면 퀵 정렬의 수행 시간은 O(n^2)이라고 말할 수 있습니다. 이러한 최악의 속도가 나오지 않게 하려고 알고리즘 초기에 피벗을 선택하는 작업을 하는 것입니다.
소스 코드
//퀵 정렬(Quick Sort)
#include <stdio.h>
#define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환
int *origin;
int on;
void QuickSort(int *base, int n);
void ViewArr(int *arr, int n);
int main(void)
{
int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };
origin = arr;
on = 10;
ViewArr(arr, 10);
QuickSort(arr, 10);
ViewArr(arr, 10);
return 0;
}
void PrintSpace(int n);
void QuickSort(int *base, int n)
{
int pivot = 0; // 피벗의 위치 기억하는 변수
int left = 0, right = 0; // 피벗보다 큰 값과 작은 값의 위치를 찾기위한 변수
if (n <= 1)
{
return;
}
left = 0;
right = n;
//퀵 소트는 피벗보다 작은 값들은 앞쪽으로 이동시키고 피벗보다 큰 값들은 뒤쪽으로 이동시켜서
//작은 값들과 큰 값들 사이에 피벗을 보내는 것이 기본 동작입니다.
//그리고 난 후에 작은 값들이 있는 배열을 재귀적으로 다시 정렬하고
//큰 값들이 있는 배열을 재귀적으로 다시 정렬하는 알고리즘입니다.
while (1)
{
//앞쪽에 피벗(인덱스 0에 있는 원소)보다 큰 값을 만날 때까지 left를 이동합니다.
//for문 맨 앞의 left를 1 증가하면서 출발하는 이유는 이전에 끝난 다음 위치부터 시작하기 위해서입니다.
for (left++; (left<n) && (base[0] >= base[left]); left++);
//뒤쪽에 피벗(인덱스 0에 있는 원소)보다 작은 값을 만날 때까지 right를 이동합니다.
for (right--; (right>0) && (base[0]<base[right]); right--);
//만약 left가 right보다 작다면 피벗과 비교했을 때 작은 값이 큰 값보다 뒤에 있으니 교환합니다.
if (left<right)
{
SWAP(base[left], base[right]);
PrintSpace(base - origin);
ViewArr(base, n);
}
//그렇지 않다면 피벗을 중심으로 작은 값들과 큰 값들이 분리 작업이 끝난 것입니다.
else
{
break;
}
}
//이제 피벗을 작은 값들과 큰 값들 사이로 보냅니다.
SWAP(base[0], base[right]);
PrintSpace(base - origin);
ViewArr(base, n);
//피벗보다 작은 값들이 있는 앞쪽을 재귀 호출로 정렬합니다.
QuickSort(base, right);
//피벗보다 큰 값들이 있는 뒤쪽을 재귀 호출로 정렬합니다.
QuickSort(base + left, n - left);
}
void PrintSpace(int n)
{
int i = 0;
for (i = 0; i<n; i++)
{
printf(" ");
}
}
void ViewArr(int *arr, int n)
{
int i = 0;
for (i = 0; i<n; i++)
{
printf("%2d ", arr[i]);
}
printf("\n");
}
다음은 시뮬레이션 용 퀵 소트 소스 코드입니다.
//퀵 정렬(Quick Sort)
#include
#include
#define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환
#define LENGTH(arr) (sizeof(arr)/sizeof(arr[0]))
enum Color
{
BLACK, BLUE, GREEN, JADE, RED, PURPLE, YELLOW, WHITE, GRAY,
LIGHT_BLUE, LIGHT_GREEN, LIGHT_JADE, LIGHT_RED, LIGHT_PURPLE, LIGHT_YELLOW, LIGHT_WHITE
};
void changecolor(int color)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}
#define MAX_ELEM 30
void QuickSort2(int* obase, int on,int *base,int n);
void MakeRandoms(int* base, int n, int end);
void ViewArr(int* arr, int n);
int main(void)
{
int arr[MAX_ELEM];
MakeRandoms(arr, MAX_ELEM, 100);
ViewArr(arr, MAX_ELEM);
QuickSort2(arr, MAX_ELEM,arr, MAX_ELEM);
ViewArr(arr, MAX_ELEM);
return 0;
}
void MakeRandoms(int* base, int n, int end)
{
srand((unsigned)time(0));
int i = 0;
for (i = 0; i < n; i++)
{
base[i] = rand() % end;
}
}
void PrintSpace(int n);
void View2(int *obase, int on, int *base, int n, int left, int right,int how);
void QuickSort2(int* obase, int on, int* base, int n)
{
int pivot = 0; // 피벗의 위치 기억하는 변수
int left = 0, right = 0; // 피벗보다 큰 값과 작은 값의 위치를 찾기위한 변수
if (n <= 1)
{
return;
}
left = 0;
right = n;
while (1)
{
Sleep(300);
for (left++; (left < n) && (base[0] >= base[left]); left++)
{
View2(obase, on, base, n, left, right,0);
}
View2(obase, on, base, n, left, right, 0);
changecolor(LIGHT_YELLOW);
PrintSpace(base - obase + left);
printf("BIG\n");
for (right--; (right > 0) && (base[0] < base[right]); right--)
{
View2(obase, on, base, n, left, right,0);
}
View2(obase, on, base, n, left, right, 0);
changecolor(LIGHT_YELLOW);
PrintSpace(base-obase+right);
printf("small\n");
if (left < right)
{
SWAP(base[left], base[right]);
View2(obase, on, base, n, left, right,1);
}
else
{
break;
}
}
SWAP(base[0], base[right]);
View2(obase, on, base, n, left, right,2);
Sleep(300);
int gap = base - obase;
if (right >1)
{
changecolor(LIGHT_YELLOW);
printf("Recursice call start:%d count:%d\n", gap,right);
}
QuickSort2(obase,on,base, right);
if (n - left >1)
{
changecolor(LIGHT_YELLOW);
printf("Recursice call start:%d count:%d\n", gap+left, n-left);
}
QuickSort2(obase,on,base + left, n - left);
}
void View2(int* obase, int on, int* base, int n, int left, int right,int how)
{
int gap = base - obase;
n += gap;
left += gap;
right += gap;
int i = 0;
for (i = 0; i < on; i++)
{
changecolor(WHITE);
if (i < gap)
{
changecolor(BLACK);
}
if (i == gap)
{
changecolor(LIGHT_RED);
if (how == 2)
{
changecolor(LIGHT_PURPLE);
}
}
if (i == left)
{
if (how == 0)
{
changecolor(LIGHT_GREEN);
}
if (how == 1)
{
changecolor(LIGHT_PURPLE);
}
}
if (i == right)
{
if (how == 0)
{
changecolor(LIGHT_PURPLE);
}
if (how == 1)
{
changecolor(LIGHT_GREEN);
}
if (how == 2)
{
changecolor(LIGHT_RED);
}
}
if (i >= n)
{
changecolor(BLACK);
}
printf("%2d ", obase[i]);
}
printf("\n");
changecolor(WHITE);
}
void ViewArr(int* arr, int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%2d ", arr[i]);
}
printf("\n");
}
void PrintSpace(int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf(" ");
}
}