원문 링크 : [펌] 퀵정렬(QuickSort] 설명
[펌] 퀵정렬(QuickSort] 설명
퀵정렬을 한마디로 기준값의 자리를 찾아내 가는 과정에서 그 기준값보다 큰것은 오른쪽에 작은것은 왼쪽으로 보내는 겁니다.
한번 손으로 해봅시다.
{7,8,3,2,1,5,9,10,4,6}
(1) 먼저 제일 오른쪽 끝 값인 “6”을 기준값으로 정합니다.
(2) 그럼 두번째 오른쪽 끝인 “4”부터 왼쪽방향으로 기준값보다 작은 숫자를 찾습니다.
이경우에는 바로 “4”가 찾아 졌내요.
(3) 이번엔 제일 왼쪽 끝에 있는 “7”부터 오른쪽방향으로 기준값보다 큰 숫자를 찾습니다.
이경우에도 바로 “7”이 해당되네요.
(4) 만일 (2)에서 찾은 수의 자리가 (3) 에서 찾은 수의 자리보다 왼쪽에 있으면 두수를 자리바꿈을 합니다.
이경우에는 바로 바꾸면 되겠네요. 그래서 이제는
{4,8,3,2,1,5,9,10,7,6} 이렇게 됩니다.
(5) 다시 위의 (2)에서 하던일(왼쪽방향으로 기준값,”6″,보다 작은 숫자를 찾는일)을 계속합니다.
“10”부터시작해서 “9”를 지나 “5”를 발견했네요.
(6) 이제는 위의 (3)에서 하던일(오른쪽방향으로 기준값,”6″,보다 큰 숫자를 찾는일)을 계속합니다.
“8”에서 시작하자마자 그냥 “8”이 해당되네요.
(7) 위의 (4)에서와 마찬 가지로 (5)에서 찾은 수가 (6) 에서 찾은 수의 자리보다 왼쪽에 있으므로 두수를 자리바꿈을 합니다. 그래서 이제는
{4,5,3,2,1,8,9,10,7,6} 이렇게 됩니다.
(8) 다시 위의 (5)에서 하던일(왼쪽방향으로 기준값,”6″,보다 작은 숫자를 찾는일)을 계속합니다.
“1”부터 시작하자마자 그냥 “1”이 해당되네요.
(9) 이제는 위의 (6)에서 하던일(오른쪽방향으로 기준값,”6″,보다 큰 숫자를 찾는일)을 계속합니다.
“3”에서 시작해서 “2”를 지나 “1”을 지나서 “8”을 찾았군요.
(10) 근데 이번에는 (8)에서 찾은 수가 (9) 에서 찾은 수의 자리보다 오른쪽에 있으므로 (9)에서 찾은 수인 “8”과 기준값인 “6”을 자리 바꿈을 하여
{4,5,3,2,1,6,9,10,7,8} 이렇게 되는데 잘 보시면 아시겠지만 기준값이었던 “6”보다 오른쪽에는 “6”보다 큰수들만 있고 왼쪽에는 “6”보다 작은수들만 있으므로 “6”은 제자리를 찾은거죠. 위에있는 수들을 다음과 같이 써봅시다.
{4,5,3,2,1} {6} {9,10,7,8}
여기서 “6”을 제외한 왼쪽에 있는 수들, {4,5,3,2,1},로 다시 퀵정렬을 하고 오른쪽에 있는 수들,{9,10,7,8}로 또 다른 퀵정렬을 하면 되는 겁니다.
그래서 퀵정렬은 재귀함수 (recursive function)을 쓰게 되는 겁니다.
말하자면 quicksort({7,8,3,2,1,5,9,10,4,6})를 부르면 그 함수안에서 결국 quicksort({4,5,3,2,1}) 와 quicksort({9,10,7,8})를 부르게 되고 또 결국 자꾸만 조그만 수들로 쪼개져서 더이상 쪼갤수 없을때까지 자기자신인 quicksort()를 계속부르게 되는 거죠.
그럼 본인이 직접 손으로 해보세요. 그러면 훨신 프로그램 만들기가 쉬울겁니다.
도움이 되었길 바랍니다.
아래의 소스는 별도로 작성한 것임.
#include <CTIME>
#include <CSTDLIB>
using namespace std;
const int N = 1000000;
inline void swap(int a[], int i, int j)
{
int t = a[i]; a[i] = a[j]; a[j] = t;
}
void CheckSort(int a[], int n)
{
int i, Sorted;
Sorted = true;
for (i=1; i < n; i++)
{
if (a[i] > a[i+1]) Sorted = false;
if (!Sorted) break;
}
if (Sorted) cout << “정렬완료.” << endl;
else cout << “정렬 오류 발생.” << endl;
}
void QuickSort(int a[], int l, int r)
{
int i, j, v;
if (r > l)
{
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);
}
}
int main()
{
int i; //, a[N+1];
double start_time;
int *a = new int[N + 1];
a[0] = -1; // 감시키
srand(time(NULL));
for (i=1; i <= N; i++) a[i] = rand();
start_time = clock();
QuickSort(a, 1, N);
cout << “퀵 정렬의 실행 시간 (N = ” << N << “) : ” << clock() – start_time << endl;
CheckSort(a, N);
delete []a;
return 0;
}