[자료구조] 퀵 정렬(quick sort )...

퀵 정렬(quick sort )은 정렬할 전체 원소에 대해서 정렬을 수행하지 않고 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다. 왼쪽 부분 집합에는 기준값보다 작은 원소들을 이동시키고, 오른쪽 부분집합에는 기준값보다 큰 원소들을 이동시킨다.
 이 때 사용하는 기준값을 피봇(pivot)이라고 하는데, 일반적으로 전체 원소 중에서 가운데에 위치한 원소를 피봇으로 선택한다.
 퀵 정렬은 다음의 두 가지 기본 작업을 반복 수행하여 완성한다.

(1)분할(divide): 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할 한다.

(2)정복(conquer) : 부분집합의 원소들 중에서 기준값보다 작은 원소들은 왼쪽 부분집합으로, 기준값보다 큰 원소들은 오른쪽 부분집합으로 정렬한다. 부분집합의 크기가 1 이하로 충분히 작지 않으면 순환 호출을 이용하여 다시 분할한다.

분할 작업을 순환적으로 반복하면서 피봇의 왼쪽 부분집합과 오른쪽 부분집합을 정렬하는 방법으로 전체 원소들을 정렬한다. 부분집합으로 분할하기 위해서는 L과 R을 사용한다. 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇보다 크거나 같은 원소를 찾아 L로 표시하고, 오른쪽 끝에서 왼쪽으로 움직이면서 피봇보다 작은 원소를 찾아 R로 표시한 후에 두 원소를 서로 교환한다. L과 R이 만나면 피봇과 R의 원소를 서로 교환하여 피봇의 위치를 확정한다.
 피봇의 확정된 위치를 기준으로 만들어진 왼쪽 부분집합과 오른쪽 부분집합에 대해서 퀵 정렬을 순환적으로 반복 수행하는데, 부분집합의 크기가 1 이하가 되면 퀵정렬을 종료한다.

간단한 퀵정렬 소스 이다.

int partition(int a[], int begin, int end)
{
 int pivot, temp, L, R ;
 L = begin ;
 R = end ;
 pivot = (begin+end)/2 ;

 while(L<R)
 {
  while((a[L]<a[pivot]) && (L<R)) L++ ;
  while((a[R]>=a[pivot]) && (L<R)) R-- ;
  if(L<R)
  {
   temp = a[L] ;
   a[L] = a[R] ;
   a[R] = temp ;
  }
 }

 temp = a[pivot] ;
 a[pivot] = a[R] ;
 a[R] = temp ;

 return L ;  
}

void quickSort(int a[], int begin, int end)
{
 if(begin<end)
 {
  int p ;
  p = partition(a, begin, end) ;
  quickSort(a, begin, p-1) ;
  quickSort(a, p+1, end) ;
 }
}

그리고 아래의 동영상을 참고 하면 퀵정렬을 이해하기 좀더 쉬울것이다.