퀵 정렬

퀵 정렬(Quicksort)은 C. A. R. 호어가 개발한 정렬 알고리즘으로, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 Θ(n²)번의 비교를 수행하고, 평균적으로 Θ(n log n)번의 비교를 수행한다.

퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 localized되있기 때문에 cache의 hit ratio가 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 퀵 정렬은 다른 Θ(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 그리고 퀵 정렬은 정렬을 위해 O(log n)만큼의 memory를 필요로한다. 또한 퀵 정렬은 불안정 정렬에 속한다.

난수열에 대해 퀵 정렬을 실행한 그림. 수평선은 피벗 값을 가리킨다.

알고리즘

퀵 정렬은 분할 해결 전략을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

예제

피벗은 p, 리스트를 둘로 나눈 각값에 대한 인덱스를 i,j라고 하자.

5 - 3 - 7 - 6 - 2 - 1 - 4    
                        p 

피벗 값보다 큰 값을 교환한다.

5 - 3 - 7 - 6 - 2 - 1 - 4 
i                   j   p 
1 - 3 - 7 - 6 - 2 - 5 - 4 
i                   j   p 

피벗 값보다 작으므로 교환하지 않는다.

1 - 3 - 7 - 6 - 2 - 5 - 4 
    i           j       p 

피벗 값보다 큰 값을 교환한다.

1 - 3 - 7 - 6 - 2 - 5 - 4 
        i       j       p 
1 - 3 - 2 - 6 - 7 - 5 - 4  
        i       j       p 

피벗 값과 정렬된 리스트 값을 교환한다.

1 - 3 - 2 - 6 - 7 - 5 - 4 
                        p 
1 - 3 - 2 - 4 - 7 - 5 - 6 
            p             

각 부분 리스트를 정렬한다.

1 - 3 - 2 
1 - 2 - 3 

완성된 리스트는 다음과 같다.

1 - 2 - 3 - 4 - 5 - 6 - 7

의사 코드와 세부 설명

퀵 소트 예제.
두꺼운 선으로 둘러싸인 원소는 피벗 원소로서, 파티션의 마지막 원소로 한 경우이다.

  function quicksort(q)
      var list less, pivotList, greater
      if length(q) ≤ 1  then
          return q  
      select a pivot value pivot from q
      for each x in q except the pivot element
          if x < pivot then add x to less
          if x ≥ pivot then add x to greater
      add pivot to pivotList
      return concatenate(quicksort(less), pivotList, quicksort(greater))

그러나 위 코드는 두 개의 작은 리스트를 저장하기 위해 Ω(n) 크기의 저장공간이 따로 필요하다는 단점이 있다. 실제 구현에서 임시 메모리는 캐시 성능과 속도에 심각한 저하를 가져올 수 있다. 아래와 같이 추가 메모리 없이 배열 내부에서 분할 작업을 구현하면 좀 더 복잡하지만 추가 메모리를 사용하지 않고 구현할 수 있다.

작은 크기의 예제 리스트에 대해 내부 분할을 적용한 그림.
두꺼운 선으로 둘러싸인 원소는 피벗 원소이다. 파란색은 피벗보다 작거나 같고 빨간색은 피벗보다 크다.

  function partition(a, left, right, pivotIndex)
      pivotValue := a[pivotIndex]
      swap(a[pivotIndex], a[right]) // 피벗을 끝으로 옮겨 놓는다.
      storeIndex := left
      for i from left to right-1
          if a[i] <= pivotValue then
              swap(a[storeIndex], a[i])
              storeIndex := storeIndex + 1
      swap(a[right], a[storeIndex]) // 피벗을 두 리스트 사이에 위치시킨다.
      return storeIndex

이것은 내부 분할 알고리즘이다. 이 알고리즘은 주어진 배열에서 pivotIndex에 위치한 값보다 작은 값들을 리스트의 앞쪽에, 큰 값들을 리스트의 맨 뒤에 몰아넣음으로써 left와 right 위치 사이의 원소들을 두 개로 분할한다. 그리고 그렇게 분할된 두 리스트 사이에 피벗을 위치시키면 피벗의 위치가 정해진다. 또한 피벗 값은 임시로 리스트의 맨 뒤에 저장해놓기 때문에 중간에 피벗의 위치가 바뀌거나 하지 않는다.

이렇게 분할 알고리즘을 구현하면 퀵 정렬은 다음과 같이 간단하게 구현할 수 있다.

  function quicksort(a, left, right)
      if right > left then
          select a pivot value a[pivotIndex]
          pivotNewIndex := partition(a, left, right, pivotIndex)
          quicksort(a, left, pivotNewIndex-1)
          quicksort(a, pivotNewIndex+1, right)

Pascal과 C와 같은 명령형 언어에서는 대부분 이와 같은 내부 분할을 이용해 구현한다.

개선된 피벗 선택

퀵 정렬에서 피벗 위치를 결정하는 방법에는 여러가지 방법이 있다. 기초적인 방법으로는 난수 분할이 사용되는데, 안정성이 떨어진다. 많은 라이브러리에서는 세 값(좌측 끝, 중앙, 우측 끝)의 중위법을 이용하여 분할한다. 이 방법을 사용하면 중앙에서 분할될 가능성이 높아 전체적으로 정렬의 성능이 좋아진다.

복잡도

$n$의 리스트를 정렬하는데 걸리는 시간을 $T(n)$, $c$는 임의의 상수라 하고, 리스트가 두 개의 거의같은 부분집합으로 나뉜다고 가정하여 얻은 평균 시간 복잡도는 다음과 같다.

$\begin{align} T(n) & \ge cn + 2T\left(\frac n 2\right) \\ & \ge cn + 2\left\{\frac{cn} 2+2T\left(\frac n 4\right)\right\}\\ & \ge 2cn + 4T\left(\frac n 4\right)\\ & \cdots\\ & \ge cn\log_2n+nT(1) = O(n\log_2n) \end{align}$

소스 코드

C

 void quickSort(int numbers[], int array_size)
 {
   q_sort(numbers, 0, array_size - 1);
 }
 void q_sort(int numbers[], int left, int right)
 {
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   pivot = numbers[left];
   while (left < right)
   {
     while ((numbers[right] >= pivot) && (left < right))
       right--;
     if (left != right)
     {
       numbers[left] = numbers[right];
       left++;
     }
     while ((numbers[left] <= pivot) && (left < right))
       left++;
     if (left != right)
     {
       numbers[right] = numbers[left];
       right--;
     }
   }
   numbers[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot)
     q_sort(numbers, left, pivot-1);
   if (right > pivot)
     q_sort(numbers, pivot+1, right);
 }

Java

public void quickSort(int left, int right)
{
   int i,j,tmp;
   TableEntry p;
 
   if(left<right)
   {
      i=left;
      j=right;
      p=table[left];
      //분할 과정
      while(i<j)
      {
         while(table[j].key>p.key)         j--;
         while(i<j && table[i].key<=p.key) i++;
 
         tmp = table[i];
         table[i]=table[j];
         table[j]=tmp;
      }
      table[left] = table[i];
      table[i]=p;
      //정렬 과정
      quickSort(left,i-1);
      quickSort(i+1,right);   
   }
}

Objective Caml(OCaml)

 let rec quicksort = function
   | [] -> []
   | pivot :: rest ->
       let is_less x = x < pivot in
       let left, right = List.partition is_less rest in
       quicksort left @ [pivot] @ quicksort right

Haskell

quicksort [] = []
quicksort (p:tl) = quicksort [ x | x <- tl, x <= p ] ++ [p] ++ quicksort [ x | x <- tl, x >  p ]