퀵 정렬

위키백과 ― 우리 모두의 백과사전.

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

퀵 정렬(Quicksort)은 C. A. R. 호어가 개발한 정렬 알고리즘이다. 퀵 정렬은 n개의 데이터를 정렬할 때 평균적으로 Θ(n log n)번의 비교를 수행하고, 최악의 경우에는 Θ(n²)번의 비교를 수행한다. 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고, 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 퀵 정렬은 다른 Θ(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 퀵 정렬은 불안정 정렬에 속한다.

[편집] 알고리즘

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

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

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

간단한 의사코드로 이 알고리즘을 아래와 같이 쓸 수 있다.

 function quicksort(q)
     var list less, pivotList, greater
     if length(q) ≤ 1  
         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
             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
         select a pivot value a[pivotIndex]
         pivotNewIndex := partition(a, left, right, pivotIndex)
         quicksort(a, left, pivotNewIndex-1)
         quicksort(a, pivotNewIndex+1, right)

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

아래는 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);
}