Soft Ware/C 언어!!

퀵정렬 이해 및 소스

달려가보자 2011. 12. 12. 14:55

퀵정렬은 정렬 중 제일 빠르다고 다들 알고 있을 것이다 .

그럼 퀵정렬를 이해부터 하고 소스에 대해 말씀드리겠습니다.

퀵정렬은 피봇이라는 기준점을 두고 왼쪽에서 오른쪽으로 증가하는 방향 과

오른쪽에서 왼쪽으로 가는 감소하는 방향으로 나눈다 .

왼쪽에서 오른쪽으로 가는 방향은 피봇보다 무조건 작아야 된다 .  만약 피봇보다 같거나 크면

증가하는것을 멈춘다.

오른쪽에서 왼쪽으로 가는 방향은 피봇보다 무조건 커야된다. 위와 비슷하게 피봇보다 작거나 같으면

감소를 멈춘다.

이 멈춘곳에 화살표가 있다고 가정해 보자 그럼 두개의 화살표가 존재 할것이다.

서로 멈춘 두개의 화살표가 가지고 있는 데이터를 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]);
}