퀵 정렬은 분할 해결 전략을 통해 리스트를 정렬한다.
- 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
- 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
http://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC#.EC.95.8C.EA.B3.A0.EB.A6.AC.EC.A6.98
#include<stdio.h>
#include<stdlib.h>
void shuffle(int *arr);
void swap(int *a, int *b);
void print(int * arr, int st, int ed);
void quick(int *arr);
void partition(int *arr,int _st, int _ed);
int main(int argc, char *argv[])
{
int arr[16];
for(int r=0; r<50; r++){
for(int i=0; i<16; i++){
arr[i] = i;
}
srand(r);
shuffle(arr);
printf("%10s : ","shuffle");
print(arr,0,15);
quick(arr);
printf("%10s : ","quick");
print(arr,0,15);
printf("=============================================================\n");
//break;
}
system("pause > nul");
return 0;
}
void quick(int *arr){
partition(arr,0,15);
}
void partition(int *arr,int _st, int _ed){
int p = _ed;
int buf_p = arr[p];
int st=_st,ed=_ed-1;
while(st<ed){
//if(st<p){
if( arr[st]<arr[p]){
st++;
continue;
}
if( arr[ed]>arr[p]){
ed--;
continue;
}
if( arr[st] > arr[ed]){
swap(arr+st, arr+ed);
}
}
//printf("st=%d,ed=%d,p=%d\n",st,ed,p);
if( st < p ){
if( arr[st]>arr[p]){
swap(arr+st, arr+p);
int t = p;
p = st;
st = t;
}
}
st = _st;
ed = _ed;
printf("(%2d)%6s : ",buf_p,"quick");
print(arr,st,ed);
if (st < p)
partition(arr, st, p-1);
if (ed > p)
partition(arr, p+1, ed);
}
void shuffle(int *arr){
int n = 100;
int a,b;
while(n--){
a = rand()%16;
b = rand()%16;
swap(arr+a,arr+b);
}
}
void swap(int *a, int *b){
int t = *a;
*a = *b;
*b = t;
}
void print(int * arr, int st, int ed){
for(int i=0; i<16; i++){
if( st<=i && i<=ed){
printf("%3d",arr[i]);
}
else{
printf(" ");
}
}printf("\n");
}
'c/c++' 카테고리의 다른 글
| 키보드 전역 후킹 예제 (2) | 2011.09.14 |
|---|---|
| 키보드 전역 후킹 (0) | 2011.08.29 |
| Console API 모음 (MSDN) (0) | 2011.07.14 |
| Console API를 이용하여 더블버퍼링 (0) | 2011.07.14 |
| 쓰레드를 이용한 행렬 곱연산 (0) | 2010.09.16 |
