퀵정렬은 정렬 중 제일 빠르다고 다들 알고 있을 것이다 .
그럼 퀵정렬를 이해부터 하고 소스에 대해 말씀드리겠습니다.
퀵정렬은 피봇이라는 기준점을 두고 왼쪽에서 오른쪽으로 증가하는 방향 과
오른쪽에서 왼쪽으로 가는 감소하는 방향으로 나눈다 .
왼쪽에서 오른쪽으로 가는 방향은 피봇보다 무조건 작아야 된다 . 만약 피봇보다 같거나 크면
증가하는것을 멈춘다.
오른쪽에서 왼쪽으로 가는 방향은 피봇보다 무조건 커야된다. 위와 비슷하게 피봇보다 작거나 같으면
감소를 멈춘다.
이 멈춘곳에 화살표가 있다고 가정해 보자 그럼 두개의 화살표가 존재 할것이다.
서로 멈춘 두개의 화살표가 가지고 있는 데이터를 SWAP을 한다.
그리고 다시 화살표들은 증가 및 감소를 하는데 여기서 오른쪽 에서 왼쪽으로 가는 화살표가
왼쪽에서 오른쪽으로 가는 화살표 보다 값이 낮다면 즉
오른쪽 화살표 | 왼쪽 화살표 |
이렇게 된다면 피봇과 오른쪽 화살표가 가르킨 대상과의 SWAP을 시킨다.
그런 후 이제부터는 배열을 반으로 쫒개서 연산을 한다 .
방법은 위에 설명과 같이 반복적으로 연산을 한다.
자 그럼 소스를 보면서 이해봅시다.
#include <stdio.h>
void quicksort(int A[], int p, int r)
{
int Left,Right;
int Temp = 0;
int pivot ;
if( p >= r) return ;
Left = p ;
Right = r+1;
pivot = A[p];
do{
do{
Left++;
}while(A[Left]<pivot);
do{
Right--;
}while(A[Right]>pivot);
if(Left < Right)
{
Temp = A[Left];
A[Left] = A[Right];
A[Right] = Temp;
}
}while(Left<Right);
Temp = A[Right];
A[Right] = A[p];
A[p] = Temp;
quicksort(A,p,Right-1);
quicksort(A,Right+1,r);
}
int main()
{
int Test[10]={1,0,3,4,6,2,7,5,8,9};
int i = 0;
quicksort(Test,0,9);
for(i=0; i < 10; i++) printf("%d\n",Test[i]);
}
'Soft Ware > C 언어!!' 카테고리의 다른 글
부동 소수점에 대해서 파헤쳐보았습니다 !!! (0) | 2012.01.27 |
---|---|
realloc을 이용한 원형 리스트 입니다 (0) | 2012.01.13 |
동적할당 과 랜덤함수를 이용하여 데이터값 넣기 (0) | 2011.12.12 |
int main(int argc, char *argv[]) 에 대해서 (0) | 2011.12.12 |
realloc 의 의미와 사용방법 (1) | 2011.12.02 |