퀵 정렬 (Quick Sort)

3줄 요약
개요
알고리즘
- 분할 교환 정렬 알고리즘
성능
- 최악의 경우 \(\Theta(n^2)\)
- 최선의 경우 \(\Theta(n \lg n)\)
  - 마스터 정리 적용
구현
개선 방법
Java의 DualPivotQuicksort 클래스
함께 읽기
참고문헌
TODO
주석

3줄 요약

주어진 데이터 배열에서 임의의 값을 하나 선택한다.
위에서 선택한 값을 기준으로, 더 작은 값을 왼쪽으로 옮겨 모으고 더 큰 값을 오른쪽으로 옮겨 모은다.
왼쪽과 오른쪽에 대해 재귀적으로 이를 반복한다.

개요

1959년 영국의 컴퓨터 과학자 Sir Antony Hoare가 고안한 정렬 알고리즘.

TAOCP

빠른정렬을 다른 방식들과 결합한다면 빠른 평균 실행 시간뿐만 아니라 최악의 경우에서의 \(O(N \log N)\) 규모의 정렬 시간을 절대적으로 보장할 수 있다. ¹

CLRS

퀵 정렬은 원소 수가 n개인 입력 배열을 최악의 경우 \(\Theta(n^2)\)에 정렬하는 알고리즘이다. 퀵 정렬은 최악의 경우에는 수행시간이 느리지만 평균 수행시간이 \(\Theta(n \lg n)\)으로 매우 효율적이고 \(\Theta(n \lg n)\) 표현에 숨겨진 상수 인자도 매우 작다. 또한 내부 정렬이라는 장점도 있고 가상 메모리 환경에서도 잘 동작해 일반적으로 실제 문제에서 가장 유용한 정렬 방법이다. ²

알고리즘

그럼 이와는 상당히 다른, 각 비교의 결과를 이용해서 다음번에 비교할 키들을 결정하는 전략을 살펴보자. 그와 같은 전략은 병렬 계산에는 부적합하지만, 직렬로 작동하는 컴퓨터에서는 상당히 이득이 된다.

여기서 말하는 방법의 기본적인 발상은 이런 것이다. 한 레코드(이를테면 \(R_1\))를 취하고, 그것을 정렬된 파일에서 차지해야 할 최종 위치(이를테면 \(s\))로 이동한다. 이 최종 위치를 결정하는 도중에, 위치 \(s\)의 왼쪽에 현재 레코드의 키보다 더 큰 키들이 존재하지 않도록, 그리고 그 오른쪽에는 그보다 더 작은 키들이 존재하지 않도록 다른 레코드들도 적절히 재배치한다. 결국 파일은 원래의 정렬 문제가 두 개의 보다 간단한 문제들, 즉 \(R_1 ... R_{s-1}\)과 \(R_{s+1} ... R_N\)을 각각 독립적으로 정렬하는 문제들이 되는 방식으로 분할된다. 각 부분파일들에도 마찬가지 기법을 적용한다. 그러다 보면 결국은 파일 전체가 제대로 정렬된다. ³

분할 교환 정렬 알고리즘

TAOCP에는 다음과 같은 분할 교환 정렬도 함께 소개된다.

파일을 왼쪽, 오른쪽 부분파일들로 분할하는 방법은 여러 가지가 있는데, 세지윅(R. Sedgewick)에서 기인한 다음과 같은 방법이 알고리즘을 분석하기에 좀 더 깔끔하다는 점에서 최선인 것 같다. ³

이 방법은 다음과 같다.

수열 \(R\)이 주어진다. 이 수열 \(R\)을 분할하며 정렬할 것이다.
- 분할은 왼쪽과 오른쪽 부분으로 나눈다.
두 개의 포인터 i, j를 둔다.
- 초기값은 i = 2, j = N이다.
- 왼쪽과 오른쪽으로 나누는 기준은 가장 왼쪽 원소이다.
만약 \(R_i\)가 분할 이후에 왼쪽 부분으로 가게 된다면, i를 1 증가한다.
- 이 과정을 오른쪽 부분파일에 속할 레코드 \(R_i\)에 도달할 때까지 반복한다.
j는 왼쪽 부분파일에 속할 레코드 \(R_j\)를 만날 때까지 계속 감소한다.
만약 \(i \le j\)이면 \(R_i\)를 \(R_j\)와 교환한다.
이 작업을 양쪽에서 \(i \ge j\)가 될 때까지 반복한다.

다음은 이 작업을 수행한 예제이다.

이 예제만 봐서는 이해가 잘 가지 않는다. 그래서 한 줄 한 줄 설명을 적어 보았다.

        i                                                                     j
[ 503  087  512  061  908  170  897  275  653  426  154  509  612  677  765  703 ]

i = 2 이므로 \(R_i = R_2 = 087\). 그리고 \(R_j = 703\).
- 087은 503보다 작다. 왼쪽 부분이다.
- 703은 503보다 크다. 오른쪽 부분이다.
- 둘 다 교환하지 않아도 된다.

             i                                       j
[ 503  087  512  061  908  170  897  275  653  426  154  509  612  677  765  703 ]

i는 한 칸씩 오른쪽으로 가다가 503보다 큰 512에서 멈춘 상태.
j는 한 칸씩 왼쪽으로 오다가 503보다 작은 154에서 멈춘 상태.
이제 512와 154의 위치를 바꾼다. (아래 그림의 ---)

                       i                        j
[ 503  087  154  061  908  170  897  275  653  426  512  509  612  677  765  703 ]
            ---                                     ---

i는 한 칸씩 오른쪽으로 가다가 503보다 큰 908에서 멈춘 상태.
j는 한 칸씩 왼쪽으로 오다가 503보다 작은 426에서 멈춘 상태.
이제 908과 426은 위치를 바꾼다.

                                 i    j
[ 503  087  154  061  426  170  897  275  653  908  512  509  612  677  765  703 ]
                      ---                      ---

똑같은 방법으로 i는 897, j는 275에서 멈춘 상태.
897과 275는 위치를 바꾼다.

                                 j    i
[ 503  087  154  061  426  170  275  897  653  908  512  509  612  677  765  703 ]
                                ---  ---

그리고 두 포인터 i, j는 서로 만난다(Pointer cross).

                                  j     i
[ 275  087  154  061  426  170 ] 503 [ 897  653  908  512  509  612  677  765  703 ]
  ---                            ---

이제 275와 503을 교환한다.
503은 정렬이 완료된 숫자가 된다.
275 ~ 170은 왼쪽으로 분할된다.
897 ~ 703은 오른쪽으로 분할된다.

이제 분할된 각 수열에 대해 같은 과정을 반복하면 된다.

이 방법은 호어(C. A. R. Hoare)⁴에서 기인한 것으로, 그의 흥미로운 논문은 지금까지 출판된 것들 중 하나의 정렬 방법에 대해 가장 상세한 설명을 담은 논문에 속한다고 할 수 있다. 호어는 그의 방법을 "빠른정렬(quicksort)"이라고 불렀는데, 그 이름은 과장이 아니다. 계산의 내부 루프들이 대부분의 컴퓨터에서 극도로 빠르기 때문이다. 한 주어진 시기에서 일어나는 모든 비교는 같은 키에 대한 것이므로, 이 키를 하나의 레지스터 안에 담아둘 수 있다. 비교들 사이에서는 색인 하나만 바꾸면 된다. 게다가 자료 이동 횟수도 상당히 적당하다. 예를 들어 표2의 경우 교환 횟수는 단 17이다.

i와 j, 그리고 스택을 제어하는 데 필요한 관리 작업이 어려운 것은 아니나, 그래도 그 작업 부담 때문에 빠른정렬의 분할 절차는 N이 상당히 클 때 가장 적합하다. ⁵

성능

퀵-정렬의 내부 루프(분할 메서드에 있는)는 인덱스를 증가시켜가며 어떤 고정된 값과 배열 항목의 값을 비교한다. 이러한 단순함이 퀵-정렬을 빠르게 하는 요인 중 하나이다. 정렬 알고리즘으로서, 이보다 더 짧은 내부 루프를 고안하기는 어렵다. 예를 들어 [[/algorithm/merge-sort]]{병합 정렬}이나 [[/algorithm/shell-sort]]{셸-정렬}이 전형적으로 더 느린 이유는 내부 루프에서 데이터 이동까지 하기 때문이다.

퀵-정렬을 빠르게 하는 두 번째 요인은 적은 수의 비교 연산을 하기 때문이다. 퀵-정렬의 효율은 종국적으로 배열을 얼마나 잘 분할 하느냐에 달려 있다. 그리고 이 부분은 어떤 항목을 분할 기준 항목으로 선택하느냐에 달려 있다. 그리고 이 부분은 어떤 항목을 분할 기준 항목으로 선택하느냐에 의해 결정된다. ⁶

퀵-정렬의 효율은 배열을 얼마나 잘 분할하느냐에 달려 있다.

최악의 경우 \(\Theta(n^2)\)

퀵 정렬에서 최악의 경우는 분할과정에서 원래의 문제를 n-1 개 짜리와 0개 짜리 부분 문제로 나누는 때다. ⁷

결론을 먼저 말하자면 최악의 경우 수행 시간은 \(\Theta(n^2)\) 이다.⁸

그런데 알고리즘 Q의 최악의 경우는 무엇일까? 알고리즘 Q가 효율적으로 처리하지 못하는 입력들이 존재할까? 이 질문에 대한 답은 상당히 당혹스럽다: 민일 원래의 파일이 이미 정렬된 순서라면, 즉 \(K_1 \lt K_2 \lt \cdots \lt K_N\)로 되어 있다면, 각 "분할" 연산은 거의 무의미하다. 부분파일의 크기를 단 하나의 원소로 줄이기 때문이다. 따라서 이런 상황(사실 정렬하기 가장 쉬운 상황이다)에서 빠른정렬은 전혀 빠르지 않다. 정렬 시간은 \(N \lg N\) 이 아니라 \(N^2\)에 비례하게 된다. (연습문제 25 참고.) 지금까지 살펴본 다른 정렬 방법들과 달리, 알고리즘 Q는 무질서한 파일을 좋아한다. ⁹

그러므로 퀵 정렬의 최악의 경우 수행시간은 고작해야 삽입 정렬 수준이다. 게다가 \(\Theta(n^2)\)이라는 수행시간은 입력 배열이 거의 완전히 정렬되어 있을 때 일어나는데, 삽입 정렬을 이용하면 오히려 대부분의 경우에 \(O(n)\) 시간에 정렬이 가능한다. ⁷

최악의 경우만 계속해서 발생하는 상황을 재귀 관계식으로 나타내면 다음과 같다.

\[\begin{align} T(n) & = T(n-1) + T(0) + \Theta(n) \\ & = T(n-1) + \Theta(n) \\ \end{align}\]

분할에 소요되는 시간은 \(\Theta(n)\).
- 분할하려면 n개의 배열 인덱스를 다 돌아야 한다.
\(T(0) = \Theta(1)\).
- 길이가 0 인 배열을 정렬하는 데에는 상수 시간이 걸린다.

이 재귀식은 어렵지 않게 \(\Theta(n^2)\)이라는 것을 알 수 있는데 그냥 다음과 같은 덧셈이기 때문이다.

\[N + (N-1) + (N-2) + ... + 1 = \frac{ N (N+1) }{ 2 }\]

재귀식을 고지식하게 풀면 다음과 같이 될 것이다.

\[\begin{align} T(n) & = T(n-1) + \Theta(n) \\ & = T(n-2) + \Theta(n) + \Theta(n) \\ & = T(n-3) + \Theta(n) + \Theta(n) + \Theta(n) \\ & = ... \\ & = n \Theta(n) \\ & = \Theta(n^2) \\ \end{align}\]

최선의 경우 \(\Theta(n \lg n)\)

\[\def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\frfr#1{\{ #1 \}}\]

가장 고른 분할은 PARTITION이 생성하는 부분 문제 두 개의 크기가 각각 \(\floor{ n/2 }\)과 \(\ceil{ n/2 } - 1\)이 되어 양쪽 모두 크기가 \(n/2\)이하인 경우다. 이 경우 퀵 정렬이 아주 빠르게 동작한다. 상한과 하한 함수, -1 과 같은 상수항을 무시한다면 수행시간에 대한 재귀 관계식은 다음이 된다.
\[T(n) = 2T( n / 2 ) + \Theta(n)\]
마스터 정리(정리 4.1)의 두 번째 경우에 따라 이 식의 해는 \(T(n) = \Theta(n \lg n)\) 이다. 따라서 재귀 호출을 할 때마다 항상 분할이 균등하게 이루어진다면 알고리즘도 (점근적으로) 빠르게 동작한다. ⁷

마스터 정리 적용

위의 인용문에서 사용한 마스터 정리는 다음과 같다.

\[T(n) = \begin{cases} \Theta(1) & \text{ if } n = 1 \\ 2T(n/2) + \Theta(n) & \text{ if } n \gt 1 \\ \end{cases}\]
이 점화식의 해는 \(T(n) = \Theta(n \lg n)\) 이다. ¹⁰

그냥 외운 답을 말하고 끝난 것 같아 싱겁다.

큰 차이는 없지만 [[/master-theorem]]에 정리된 일반형 마스터 정리 \(T(n) = aT( { n \over b } ) + \Theta( n^k \log^p n )\)도 사용해 보자.

\(T(n) = 2T( n / 2 ) + \Theta(n)\) 이므로, a, b… 등의 값은 다음과 같다.

\(a = 2\), \(b = 2\), \(k = 1\), \(p = 0\).
\(b^k = 2^1 = 2\).
- 그러므로 \(a = b^k\) 이고, \(p \gt -1\) 이다. 마스터 정리 2-a를 사용할 수 있다.

마스터 정리 2-a는 다음과 같다.

\[T(n) = \Theta(n^{ \log_b^a } \log^{p+1} n)\]

각 값을 대입해 보면 다음과 같이 된다.

\[\begin{align} T(n) & = \Theta(n^{ \log_b^a } \log^{p+1} n) \\ & = \Theta(n^{ \log_2^2 } \log^1 n) \\ & = \Theta(n \log n) \\ \end{align}\]

구현

import java.util.Arrays;
import java.util.Collections;

public class QuickSort {
  /**
   * 주어진 배열을 정렬합니다.
   *
   * @param array 정렬 대상 배열
   */
  public static void sort(Comparable[] array) {
    // 입력 특성에 대한 종속성을 제거한다.
    Collections.shuffle(Arrays.asList(array));
    sort(array, 0, array.length -1);
  }

  /**
   * 주어진 배열의 부분 집합을 정렬합니다.
   *
   * @param array 전체 배열
   * @param left 정렬 대상 부분 집합의 시작 인덱스
   * @param right 정렬 대상 부분 집합의 마지막 인덱스
   */
  private static void sort(Comparable[] array, int left, int right) {
    if (right <= left) {
      return;
    }
    // 분할해 정렬한 다음, 새로운 기준을 얻는다.
    final int j = partition(array, left, right);
    sort(array, left, j -1 ); // 새로운 기준의 왼쪽 배열을 정렬한다.
    sort(array, j+1 , right); // 새로운 기준의 오른쪽 배열을 정렬한다.
  }

  /**
   * 배열의 부분 집합을 분할해 정렬하고, 분할 인덱스를 리턴한다.
   *
   * @param array 전체 배열
   * @param left 정렬 대상 부분 집합(왼쪽) 시작 인덱스
   * @param right 정렬 대상 부분 집합(오른쪽) 마지막 인덱스
   * @return
   */
  private static int partition(Comparable[] array, int left, int right) {
    int i = left;     // i 는 왼쪽부터 시작
    int j = right+1;  // j 는 오른쪽부터 시작
    final Comparable v = array[left];  // 기준: 가장 왼쪽 원소

    while (true) {
      // 기준보다 큰 원소를 찾는다
      while (less(array[++i], v)) {
        if (i == right) {
          break;
        }
      }
      // 기준보다 작은 원소를 찾는다
      while (less(v, array[--j])) {
        if (j == left) {
          break;
        }
      }
      if (i >= j) {
        break;
      }
      // 기준보다 큰 원소를 기준의 오른쪽으로 보내고,
      // 기준보다 작은 원소를 기준의 왼쪽으로 보낸다.
      exchange(array, i, j);
    }
    // i, j 가 만나면 기준을 왼쪽 부분의 마지막으로 옮긴다.
    // 이로 인해 기준 아이템 하나의 정렬이 완료된다. (기준 왼쪽은 모두 기준보다 작고, 기준 오른쪽은 모두 기준보다 크다)
    exchange(array, left, j);
    return j;
  }

  /**
   * 두 아이템의 위치를 교환한다.
   */
  private static void exchange(Comparable[] array, int i, int j) {
    Comparable temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  /**
   * a 가 b 보다 작다면 true를 리턴하고, 그 외의 경우 false를 리턴합니다.
   */
  private static boolean less(Comparable a, Comparable b) {
    return a.compareTo(b) < 0;
  }
}

개선 방법

정렬 대상이 매우 큰 배열이거나, 대상 배열의 특성을 알 수 없는 상황이라면 다음과 같은 개선 사항들을 적용하고 테스트해볼 가치가 있다.

삽입 정렬 전환

작은 부분 배열에서는 퀵-정렬이 [[/insertion-sort]]{삽입 정렬}보다 느리다.

재귀적 동작으로 인해, 작은 부분 배열에 대해서도 반드시 퀵-정렬의 sort()가 호출된다.¹¹

퀵 소트는 정렬 대상이 작은 부분 배열일 경우 [[/insertion-sort]]{삽입 정렬}을 사용하면 성능이 개선될 확률이 높다.

삽입 정렬 사용의 기준이 되는 cutoff 최적값에 대하여
- 로버트 세지윅에 의하면 컷 오프를 위한 최적값은 시스템에 따라 달라질 수 있으나, 5 ~ 15 정도의 값이 효과적이라 한다.¹¹
- 한편 존 벤틀리는 1,000,000으로 n을 고정한 상태에서 cutoff 값을 1부터 100까지 바꿔가며 실험해본 결과 cutoff 값이 50일 때의 결과가 좋았다고 한다.¹²

존 벤틀리는 로버트 세지윅의 방식을 소개하며 다음과 같이 설명한다.

우리의 퀵 정렬은 아주 작은 부분배열을 정렬하는 데 상당히 많은 시간을 소모하고 있다. 이런 부분은 퀵 정렬의 모든 절차를 다 사용하는 것보다는 삽입정렬과 같은 단순한 방법을 사용하는 것이 더 빠를 것이다. Bob Sedgewick은 이런 아이디어를 적용하여 아주 훌륭한 방법을 개발했다. 퀵 정렬이 작은 부분 배열(즉 \(l\)과 \(u\)가 가까울 때)에 대해 호출된 경우에는 아무것도 하지 않는다. 이것은 함수 내의 첫 번째 if문을 다음과 같이 변경하여 구현할 수 있다.
if u-l < cutoff
   return
cutoff 는 작은 정수다. 프로그램이 끝났을 때 배열은 정렬된 상태가 아니겠지만, 랜덤하게 나열된 요소를 가지는 작은 덩어리들로 나누어져 있을 것이고, 한 덩어리 안의 요소들은 오른쪽에 있는 다른 덩어리 안의 요소들보다 작은 값을 가질 것이다. 우리는 이들 덩어리 내부의 요소들을 다른 정렬 방법을 사용하여 정리해야 한다. 배열이 거의 정렬된 상태이므로 이 작업에는 삽입 정렬을 이용하는 것이 가장 적절하다. 따라서 배열 전체를 정렬하는 데는 다음과 같이 한다.
qsort4(0, n-1)
isort3()
¹³

다음은 존 벤틀리가 작성한 예제 qsort4 함수를 포맷을 일부 변경하고 주석을 추가해서 내가 옮긴 것이다.

void qsort4(l, u)
  if u - l < cutoff
    // 범위가 cutoff 미만이면 qsort로 정렬하지 않는다.
    // qsort가 다 끝난 후에 삽입 정렬 isort로 정렬한다.
    return
  swap(l, randint(l ,u))
  t = x[l];  i = l;  j = u+1;
  loop
    do i++; while i <= u && x[i] < t
    do j--; while x[j] > t
    if i >= j
      break
    temp = x[i];  x[i] = x[j];  x[j] = temp;
  swap(l ,j)
  qsort4(l, j-1)
  qsort4(j+1, u)

3-중앙값 분할 (Median-of-three partitioning)

분할 기준 항목을 정할 때 작은 크기의 샘플에서 그 중앙값(median)을 이용하는 것이다. 이렇게 하면 조금 더 효율적으로 분할을 할 수 있다. 단, 중앙값을 계산하는 추가 비용이 따른다. 대부분의 경우, 3개의 샘플을 선택하고 그 중간 항목으로 분할할 때 개선 효과를 볼 수 있다는 것이 알려져 있다. 그리고 보너스로, 샘플링되는 항목들을 배열 경계에 대한 보초로 활용하여 partition()에서 경계 테스트를 제거할 수도 있다.¹¹

분할 기준을 결정할 때, 샘플 3개를 뽑아 중간값을 사용한다는 것.

3중 분할 퀵 정렬

퀵 소트는 배열을 두 부분으로 쪼개며 작업한다. 그러나 이 방법은 세 부분으로 쪼개며 작업을 한다.

피벗 v 보다 작은 부분
피벗 v 와 같은 부분
피벗 v 보다 큰 부분

이 방법은 2중 분할 방식보다 교환 횟수가 더 많아서 별로 선호되지 않았으나, 1993년 11월 존 벤틀리(Jon Bentley)와 더글라스 맥일로이(Douglas McIlroy)가 새로운 방식의 더 빠른 3중 분할 방법을 만들어냈다.

1990년대 벤틀리(J. Bentley)와 맥일로이(D. McIlroy)가 그러한 문제를 극복할 수 있는 정교한 구현을 고안해 낸다.

그 방법을 사용하면 많은 수의 중복 키가 있는 실제적인 응용 상황에서 3-중 분할 퀵-정렬이 병합 정렬 등 다른 방법들보다 점근적으로 더 빠르다는 것이 관찰되었다.

나중에 벤틀리(J. Bentley)와 세지윅(R. Sedgewick)이 그 관찰 결과가 사실임을 증명해 내었다. ¹⁴

"중복 키가 있는 경우"에 주목하자.

표준 퀵-정렬과 마찬가지로 배열 크기가 커질수록 실행 시간이 평균에 근접하고 평균에서 크게 차이가 날 가능성이 극히 낮아진다. 따라서 3-중 퀵-정렬의 실행 시간이 배열 크기 N에 키들이 분포한 엔트로피를 곱한 값에 비례한다고 보아도 안전하다. 실용적으로도 알고리즘이 이러한 속성을 가지는 것은 중요한 의미가 있다. 이러한 속성은 중복 키가 매우 많은 경우, 실행 시간을 선형 로그에서 선형으로 줄여준다. 입력 배열에서 키들이 나열된 순서는 전혀 중요하지 않다. 왜냐하면 알고리즘 자체적으로 최악 조건을 피하기 위해 정렬 전에 무작위로 뒤섞기 때문이다.¹⁵ 키의 분포는 엔트로피를 규정하고, 그 어떤 비교 기반 알고리즘도 엔트로피에서 필요로 하는 비교 횟수보다 적은 수의 비교 연산으로 정렬을 완료할 수 없다. 3-중 퀵-정렬은 중복 키에 대응할 수 있는 능력 때문에 많은 수의 중복 키가 드물지 않은 응용 환경이라면 우선적으로 고려해야 할 정렬 알고리즘이다. ¹⁶

정렬 예

초기 상태. i = 0, lt = 0, gt = last. pivot v는 가장 왼쪽에 있는 103 값으로 할당해 둔다.

  i,lt                                     gt
[ 103  100  104  103  108  101  104  103  111 ]

i가 보는 숫자가 pivot과 같으므로 i++ 한다.

   lt   i                                  gt
[ 103  100  104  103  108  101  104  103  111 ]

pivot인 103과 i를 비교한다. 100 < 103 이므로 lt와 i를 서로 교환한다. 그리고 lt++, i++ 한다.

        lt   i                             gt
[ 100  103  104  103  108  101  104  103  111 ]

pivot인 103과 i를 비교한다. 104 > 103이므로, gt와 i를 서로 교환한다. 그리고 gt-- 한다.

        lt   i                        gt
[ 100  103  111  103  108  101  104  103  104 ]

pivot인 103과 i를 비교한다. 111 > 103이므로, gt와 i를 서로 교환한다. 그리고 gt-- 한다.

        lt   i                   gt
[ 100  103  103  103  108  101  104  111  104 ]

i가 보는 숫자가 pivot과 같으므로 i++ 한다.

        lt        i              gt
[ 100  103  103  103  108  101  104  111  104 ]

i가 보는 숫자가 pivot과 같으므로 i++ 한다.

        lt             i         gt
[ 100  103  103  103  108  101  104  111  104 ]

pivot인 103과 i를 비교한다. 108 > 103이므로, gt와 i를 서로 교환한다. 그리고 gt-- 한다.

        lt             i    gt
[ 100  103  103  103  104  101  108  111  104 ]

pivot인 103과 i를 비교한다. 104 > 103이므로, gt와 i를 서로 교환한다. 그리고 gt-- 한다.

        lt            i,gt
[ 100  103  103  103  101  104  108  111  104 ]

pivot인 103과 i를 비교한다. 101 < 103 이므로 lt와 i를 서로 교환한다. 그리고 lt++, i++ 한다.

             lt        gt   i
[ 100  101  103  103  103  104  108  111  104 ]

이제 i가 gt보다 커졌으므로, 페이즈가 끝났다.
lt 부터 gt까지는 정렬이 완료되었다.
다음 정렬 대상은 [0, lt)와 (gt, END] 이다. 이 구간들에 대해 재귀적으로 정렬한다.

             lt        gt
[ 100  101  103  103  103  104  108  111  104 ]
  --------                 ------------------
  다음 정렬 대상               다음 정렬 대상

3중 분할 퀵 정렬의 구현

public class QuickSort3Way {
  /** 주어진 배열을 정렬합니다. */
  public static void sort(Comparable[] array) {
    // 입력 특성에 대한 종속성을 제거한다.
    Collections.shuffle(Arrays.asList(array));
    sort(array, 0, array.length -1);
  }

  /** 주어진 배열을 정렬합니다.  */
  public static void sort(Comparable[] array, int lo, int hi) {
    if (hi <= lo) {
      return;
    }
    int lt = lo, i = lo + 1, gt = hi;
    Comparable v = array[lo];
    while (i <= gt) {
      int cmp = array[i].compareTo(v);
      if (cmp < 0) {
        exchange(array, lt++, i++);
      } else if (cmp > 0) {
        exchange(array, i , gt--);
      } else {
        i++;
      }
    }
    sort(array, lo, lt - 1);
    sort(array, gt + 1, hi);
  }

  /** 두 아이템의 위치를 교환한다. */
  private static void exchange(Comparable[] array, int i, int j) {
    Comparable temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}

Java의 DualPivotQuicksort 클래스

Java의 Arrays.sort() 코드를 읽어보면 경우에 따라 세 가지 정렬 중 하나를 골라 사용한다는 것을 알 수 있다.

LegacyMergeSort: 병합 정렬
- -Djava.util.Arrays.useLegacyMergeSort=true를 설정한 상태에서, Object[]를 정렬하려 하면 사용한다.
ComparableTimSort: Tim 정렬
- Object[]를 정렬하려 하면 사용한다.
DualPivotQuicksort: 2중 pivot 퀵 정렬

그 중 DualPivotQuicksort의 클래스 주석을 읽어보면, 거장들의 이름이 보인다. 이 클래스는 상당히 세심하게 튜닝된 퀵 정렬 코드를 제공한다. 잘 읽어보면 경우에 따라 힙 정렬, 삽입 정렬로의 컷 오프도 하고 있음을 알 수 있다.

/**
 * This class implements powerful and fully optimized versions, both
 * sequential and parallel, of the Dual-Pivot Quicksort algorithm by
 * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * There are also additional algorithms, invoked from the Dual-Pivot
 * Quicksort, such as mixed insertion sort, merging of runs and heap
 * sort, counting sort and parallel merge sort.
 *
 * @author Vladimir Yaroslavskiy
 * @author Jon Bentley
 * @author Josh Bloch
 * @author Doug Lea
 *
 * @version 2018.08.18
 *
 * @since 1.7 * 14
 */
final class DualPivotQuicksort {

함께 읽기

[[/master-theorem]]
[[/algorithm/merge-sort]]
[[/algorithm/shell-sort]]

참고문헌

[CLRS] Introduction to Algorithms 3판 / 토머스 코멘, 찰스 레이서손, 로날드 리베스트, 클리포드 스타인 공저 / 문병로, 심규석, 이충세 공역 / 한빛아카데미 / 2014년 06월 30일
[KNU] The art of computer programming 3 정렬과 검색(개정2판) / 도널드 커누스 저 / 한빛미디어 / 초판 2쇄 2013년 02월 10일
[PRO] 생각하는 프로그래밍 / 존 벤틀리 저 / 윤성준, 조상민 공역 / 인사이트(insight) / 초판 6쇄 발행 2007년 07월 20일
[SED] 알고리즘 [개정4판] / 로버트 세지윅, 케빈 웨인 저/권오인 역 / 길벗 / 초판발행 2018년 12월 26일

TODO

Beautiful Code에 수록된 존 벤틀리의 퀵 소트와 관련된 글을 읽고 필요하다면 인용하거나 정리해 추가할 것.

주석

[KNU] 5.2.2장. 155쪽. ↩
[CLRS] 7장. ↩
[KNU] 5.2.2장. 145쪽. ↩ ↩²
퀵 정렬을 고안한 컴퓨터 과학자. ↩
[KNU] 5.2.2장. 147쪽. ↩
[SED] 2장. 292쪽. ↩
[CLRS] 7.2장. ↩ ↩² ↩³
'쎄타 엔 제곱'으로 읽으면 된다. ↩
[KNU] 5.2.2장. 154쪽. ↩
[CLRS] 4장. ↩
[SED] 2장. 295쪽. ↩ ↩² ↩³
생각하는 프로그래밍. 402쪽. ↩
생각하는 프로그래밍. 11장. 229쪽. ↩
[SED] 2장. 297쪽. ↩
퀵 소트 자체 알고리즘이 아니라, 정렬 작업 전에 미리 섞어두는 것을 말한다. 예제 코드의 Collections.shuffle 사용 부분 참고. ↩
[SED] 2장. 300쪽. ↩