(4) 퀵 정렬법(Quick Sorting)

(4) 퀵 정렬법(Quick Sorting)

퀵 정렬의 기본 동작은 정렬하고자 하는 리스트에서 하의기준이 되는 키를 선정하여 기준키를
적당한 위치로 이동하는 것이다. 이때 리스트에서 기준키를 경계로 기준키보다 앞에 있는 키들은
모두 기준키보다 작거나 같으며 기준키보다 뒤에 있는 키들은 모두 기준키보다 크거나 같게 만
든다. 다음과 같은 키들로 구성된 리스트를 생각해 보자.

리스트의 첫 원소를 기준키로 선정한 후 다음과 같은 동작을 수행한다. 기준키 바로 다음의 위치
부터 뒤쪽으로 기준키보다 큰 키를 찾으며, 동시에 리스트의 마지막 키부터 앞쪽으로 지준키보다
작은 키를 찾아 서로 교환한다. 위의 예에서 기준키는 17로 잡게 되며, 기준키보다 큰 키는 26이
되고 기준키보다 작은 키는 2가 되어 서로 교환을 하면 다음과 같은 리스트가 된다.

계속해서 다음 키부터 이러한 동작을 반복하면 기준키 17보다 큰 키는 24가 되고 작은 키는 8이
되어 서로 교환하면 다음과 같은 리스트가 된다.

이러한 동작을 계속하면 기준키 17보다 큰 키는 24가 되고 작은 키는 6이 되는 위치를 찾게 된
다. 그러나 이번에는 아래의 리스트와 같이 앞쪽에서부터 큰 키를 찾은 위치와 뒤쪽에서부터 작
은 키를 찾은 위치가 서로 교차했음을 알 수 있다.

이 경우, 두 키값을 교환하지 않으며 그대신 기준키와 작은 키를 서로 교환하여 다음과 같은 리스
트를 만든다.

위의 리스트에서 지준키 17을 경계로 앞쪽 키들은 모두 기준키보다 작으며 뒤쪽 키들은 모두
17보다 큰 것을 알 수 잇다. 따라서 기준키 17은 전체 리스트가 정렬이 된 후에도 위치 변동이 없
게 된다. 위에서 설명된 기본 동작은 기준키를 제 위치에 놓은 후 원래의 리스트를 앞쪽 키들로
구성된 리스트와 뒤쪽 키들로 구성된 리스트로 양분하므로 이를 분할(Partition)이라 부른다. 먼
저 전체 리스트를 분할하여 2개의 리스트로 만들고 분할된 2개의 리스트에 각각 다시 분할을 적
용한다. 이러한 반복된 분할을 적용할 때 편의상 왼쪽 리스트를 먼저 분할한다. 앞에서 사용된
예에 대하여 분할을 반복 수행하여 전체 리스트의 정렬을 완로하는 퀵 정렬법의 예는 그림 6에 주
어진다. 그림 6에서 m과 n은 분할을 수행할 리스트의 범위를 나타낸다.

일반적으로 기준키는 항상 분할하고자 하는 리스트의 첫 번째 키로 선정되는데 이러한 선정 방법
을 사용하여 퀵 정렬을 C 프로그램으로 작성하면 프로그램 7-4와 같다. 그러나 리스트의 다른
키를 기준키로 선정하는 프로그램을 작성하려면 선정된 키와 리스트의 첫 번째 키를 먼저 교환
후 리스트 9를 이용하면 가능하다.

(리스트 9) 퀵 정렬
#define      MAXINT     30000
void Quick_Sort(int m,int n)   /* m과 n은 적용범위의 시작과 끝 위치 */
{
   int i,j,k,temp;

   if (m<n)
   {
      i=m;j=n+1;
      k=key[m];            /* 기준키 */
      do {                 /* 분할을 수행하는 do...while 문 */
         do {              /* 앞에서부터 기준키보다 큰 키 찾기 */
            i=i+1;
         } while (record[i]<k);

         do {              /* 뒤에서부터 기준키보다 작은 키 찾기 */
            j=j-1;
         } while (record[j]>k);

         if (i<j)
         {                  /* 큰 키와 작은 키의 교환 */
            temp=key[j];
            key[j]=key[i];
            key[i]=temp;
         }
      } while (i<=j);
      temp=key[j];          /* 기준키와 작은 키의 교환 */
      key[j]=key[m];
      key[m]=temp;
      Quick_Sort(m,j-1);    /* 앞쪽 리스트에 대한 분할을 계속 */
      Quick_Sort(j+1,n);     /* 뒤쪽 리스트에 대한 분할을 계속 */
   }
}

퀵 정렬의 분석

리스트 9의 Quick_Sort에서 최악의 경우는 매분할이 수행된 후 남은 킷값들이 모두 한쪽의
리스트에 포함되는 것이다. 예를 들면 아래와 같이 이미 정렬된 리스트가 입력될 때 최악의 경우
에 해당한다.

따라서 n개의 키를 갖는 리스트에 대하여 최악의 경우 적용되는 분할의 횟수는 n-1번이며 매
분할에 사용되는 비교의 횟수는 적용되는 리스트에 포함된 키들의 수에 비례한다. 그러므로 총
소요 시간은 n+(n-1)+........+2에 비례하게 되며 O(n²)으로 표시된다.
최악의 경우와는 반대로 최선의 경우는 매분할이 수행된 후 2개의 리스트가 같은 크기로 항상
나누어지는 것으로 소요시간은 O(nlog₂n)이며 평균 소요 시간도 역시 O(nlog₂n)이라고 알려져
있다.