11장 정렬, 집합, 선택(1)

11.1 병합 정렬

병합 정렬(merge-sort) : 재귀를 사용하여 간단하고 간결한 방법으로 설명할 수 있는 정렬 기법

11.1.1 분할 및 정복

병합 정렬(merge-sort)은 분할정복(divide and conquer)이라고 불리는 알고리즘 설계 패턴을 기반으로 한다. 

분할정복 패턴은 다음 세 단계로 구성된다:

1. 분할(divide):

    입력 크기가 특정 임계값(예를 들어, 한 개 또는 두 개의 요소)보다 작으면 

    간단한 방법으로 직접 문제를 해결하고 얻은 해결책을 반환한다. 

    그렇지 않으면 입력 데이터를 두 개 이상의 서로 다른 부분 집합으로 분할한다.
2. 반복(recur): 하위 집합과 관련된 하위 문제를 반복적으로 해결한다.
3. 정복(concur): 하위 문제에 대한 해결책을 가지고 원래 문제에 대한 해결책으로 "통합"한다.

정렬에 분할정복 사용

정렬 문제에서 우리는 n개의 객체들로 이루어진 일련의 배열과 

이 객체들에 대한 전체 순서를 정의하는 comparator를 제공받고, 

이 객체들에 대한 정렬된 표현을 요구받는다. 

두 표현 중 하나를 정렬할 수 있도록 

정렬 알고리즘을 시퀀스에 대한 높은 수준에서 설명하고, 

연결 리스트나 배열에 대해 구현하는 데 필요한 세부 사항을 설명할 것이다. 

n개의 원소로 이루어진 시퀀스 S를 

세 번의 분할 및 정복 단계를 사용하여 정렬하기 위해 

병합 정렬 알고리즘은 다음과 같이 진행된다:

1. 분할: 

    만약 S가 0이나 1개의 원소를 가지면, S를 즉시 되돌려준다. 

    그렇지 않으면(S는 적어도 2개의 원소를 가지므로), 

    S에서 모든 원소를 제거하고 S1과 S2라는 두 개의 수열에 넣는데, 

    각각 S의 원소는 약 절반을 포함한다. 

    즉, S1은 S의 첫 번째 n/2 원소를 포함하고, S2는 나머지 n/2 원소를 포함한다.
2. 반복: 시퀀스 S1 및 S2를 재귀적으로 정렬한다.
3. 정복: 정렬된 수열 S1과 S2를 정렬된 수열로 병합하여 원소를 S에 다시 넣는다.

분할 단계와 관련하여, 

표기 ⌈x⌉ = x의 천장(ceiling) = x ≤ m이 되도록 하는 가장 작은 정수 m

표기 ⌊x⌋ = x의 바닥(floor) = k ≤ x가 되도록 하는 가장 큰 정수 k

병합 정렬 트리(merge-sort tree): 병합 정렬 알고리즘의 실행을 시각화하는 이진 트리 T

T의 각 노드 - 병합 정렬 알고리즘의 재귀적 호출(또는 호출)

T의 각 노드 v - v와 연관된 호출에 의해 처리되는 수열 S

노드 v의 자식들 -  S의 하위 수열 S1과 S2를 처리하는 재귀적 호출 

T의 외부 노드들 - 재귀적 호출을 하지 않는 알고리즘의 인스턴스에 대응하는 S의 개별 요소

그림 11.1은 병합 정렬 트리의 각 노드에서 처리된 입력과 출력 시퀀스를 보여줌으로써 

병합 정렬 알고리즘의 실행을 정리한 것이다. 

병합 정렬 트리의 단계별 진행을 그림 11.2부터 그림 11.4까지 나타내었다.

 

이러한 병합 정렬 트리에 대한 알고리즘 시각화는 

병합 정렬 알고리즘의 실행 시간을 분석하는 데 도움이 된다. 

특히 병합 정렬의 재귀적 호출 시마다 병합 정렬의 크기가 대략 절반으로 줄어들기 때문에 

병합 정렬 트리의 높이는 log n 정도이다

(로그의 기본값은 생략된 경우 2임을 상기).

그림 11.1: 

(a) T의 각 노드에서 처리된 입력 시퀀스들; 

(b) T의 각 노드에서 생성된 출력 시퀀스들, 

8개의 요소들로 이루어진 시퀀스 상에서 

병합 정렬 알고리즘의 실행을 위한 병합 정렬 트리 T.

그림 11.2: 병합 정렬 실행의 시각화. 

트리의 각 노드 - 병합 정렬의 재귀적 호출

점선으로 그려진 노드 - 아직 이루어지지 않은 호출

굵은 선으로 그려진 노드 - 현재 호출

가는 선으로 그려진 빈 노드 - 완료된 호출

나머지 노드(가느다란 선으로 그어지고 비어 있지 않음) - 자식 호출이 돌아오기를 기다리는 호출

(그림 11.3에서 계속)

그림 11.3: 병합-정렬 실행의 시각화 (그림 11.4에서 계속)

그림 11.4: 병합 정렬 실행의 시각화. 

(l)과 (m)사이 및 (m)과 (n)사이에서 여러 호출이 생략된다. 

(p) 단계에서 수행된 정복 단계를 참고하자(그림 11.3에서 계속).

제안 11.1: 

크기 n의 시퀀스에 대한 병합 정렬의 실행과 연관된 병합 정렬 트리는 높이 logn을 갖는다.

이 명제를 이용하여 병합 정렬 알고리즘의 실행 시간을 분석할 것이다.

병합 정렬에 대한 개요와 작동 원리에 대한 설명을 제공한 후, 

이 분할 정복 알고리즘의 각 단계를 더 자세히 살펴보도록 하겠다. 

병합 정렬 알고리즘의 분할 및 반복 단계는 간단하며, 

크기가 n인 시퀀스를 인덱스 n/2인 요소에서 분할하는 것을 포함하고, 

재귀적 호출은 이러한 작은 시퀀스를 매개 변수로 전달하는 것을 포함한다. 

어려운 단계는 정렬된 두 시퀀스를 하나의 정렬된 시퀀스로 병합하는 정복 단계이다. 

따라서 병합 정렬에 대한 분석을 제시하기 전에, 

이것이 어떻게 수행되는지에 대해 더 자세히 설명해야 한다.

11.1.2 배열과 리스트 병합

두 정렬된 시퀀스를 병합하려면 

배열로 구현되었는지 리스트로 구현되었는지 확인하는 것이 도움이 된다. 

따라서 이 절에서 배열과 연결 리스트로 표시되는

두 정렬된 시퀀스를 병합하는 방법을 설명하는 자세한 의사 코드를 제공한다.

두 정렬된 배열 병합

코드 조각 11.1에서 보여주는 배열 구현부터 시작한다. 

그림 11.5에서 두 정렬된 배열을 병합하는 단계를 보여준다.
코드 조각 11.1: 두 개의 정렬된 배열 기반 시퀀스를 병합하는 알고리즘.

Algorithm merge(S1, S2, S):

       Input: Sorted sequences S1 and S2 an empty sequence S, all of which are

           implemented as arrays

        Output: Sorted sequence S containing the elements from S1 and S2

        i ← j ← 0

        while i < S1. size() and j < S2.size() do

            if S1.get(i) ≤ S2.get(j) then 

               S.addLast(S1.get(i))   { copy ith element of S1 to end of S }

               i ← i + 1

            else

               S.addLast(S1.get(j))   { copy jth element of S2 to end of S }

               j ← j + 1

        while i < S1. size() do   { copy the remaining elements of S1 to S }

            S.addLast(S1.get(i)) 

            i ← i + 1

        while i < S2. size() do   { copy the remaining elements of S2 to S }

            S.addLast(S2.get(j)) 

            j ← j + 1

그림 11.5: 정렬된 두 배열을 병합하는 단계이다. 

(a)의 복사 단계 이전과 (b)의 복사 단계 이후의 배열을 보여준다.

 

정렬된 두 리스트 병합하기

 

코드 조각 11.2에서는 

연결 리스트로 구현된 두 정렬된 시퀀스 S1과 S2를 병합하기 위한 

리스트 기반 버전의 알고리즘 merge를 제공한다. 

 

주요 아이디어는 

두 리스트 중 하나의 앞에서 가장 작은 요소를 반복적으로 제거하고 

출력 순서의 끝인 S에 추가하여 

두 입력 리스트 중 하나가 비어 있을 때까지 

다른 리스트의 나머지를 S에 복사하는 것이다.

 

그림 11.6에서 이 버전의 알고리즘 merge의 예제를 보여준다.

코드 조각 11.2: 

연결 리스트로 구현된 두 정렬된 시퀀스를 병합하기 위한 알고리즘 merge.

Algorithm merge(S1, S2, S):

       Input: Sorted sequences S1 and S2 an empty sequence S, implemented as

            linked lists

        Output: Sorted sequence S containing the elements from S1 and S2

        while S1 is not empty and S2 is not empty do

            if S1.first().element() ≤ S2.first().element() then 

               { move the first element of S1 at the end of S }

               S.addLast(S1.remove(S1.first()))

            else

              { move the first element of S2 at the end of S }

              S.addLast(S2.remove(S2.first()))

        { move the remaining elements of S1 to S }

        while S1 is not empty do 

            S.addLast(S1.remove(S1.first()))

        { move the remaining elements of S2 to S }

        while S2 is not empty do 

            S.addLast(S2.remove(S2.first()))

병합을 위한 실행 시간

우리는 몇 가지 간단한 관찰을 통해 merge 알고리즘의 실행 시간을 분석한다. 

n1: S1의 원소의 개수

n2: S2의 원소의 개수

알고리즘 merge에는 세 개의 while 루프가 있다. 

배열 기반 버전과 리스트 기반 버전 중 어느 것을 분석하든 상관없이, 

각 루프 안에서 수행되는 연산은 각각 O(1) 시간이 걸린다. 

핵심적인 관찰은 한 루프를 반복할 때마다 

한 개의 원소가 S1 또는 S2에서 S로 복사되거나 이동되는 것이다. 

S1이나 S2에는 삽입이 없으므로, 

이 관찰은 세 루프의 전체 반복 횟수가 n1 + n2임을 의미한다. 

알고리즘 merge의 실행 시간: 0(n1 + n2)

그림 11.6: 코드 조각 11.2에 나타난 알고리즘 merge의 실행 예.

11.1.3 병합 정렬의 실행 시간

이제 병합 정렬 알고리즘의 세부 사항을 

배열 기반 버전과 리스트 기반 버전 모두에 제공하고 

정복 단계에 사용된 중요한 병합 알고리즘의 실행 시간을 분석했으므로 

n개 요소의 입력 순서가 주어졌다고 가정하고 

전체 병합 정렬 알고리즘의 실행 시간을 분석해 보겠다. 

단순화를 위해 n이 2의 거듭제곱인 경우로 주의를 제한한다. 

분석 결과가 n이 2의 거듭제곱이 아닐 때도 유지된다는 것을 보여주기 위해

연습(R-11.6)에 맡긴다.

merge 알고리즘의 분석에서 했던 것처럼, 

병합 정렬의 각 재귀적 호출에 의해 생성된 입력 시퀀스 S와 보조 시퀀스 S1 및 S2가 

배열 또는 연결 리스트(S와 동일)으로 구현되어 

두 정렬된 시퀀스를 선형 시간에 병합할 수 있다고 가정한다.

앞서 언급한 것처럼 병합 정렬 트리 T를 참조하여 병합 정렬 알고리즘을 분석한다

(그림 11.2~11.4 참조). 

 

T의 노드 v에서 보낸 시간

= v의 자식들과 연관된 반복적 호출이 종료될 때까지 걸리는 시간을 제외하고

   v와 연관된 반복적 호출의 실행 시간

= 분할 및 정복 단계의 실행 시간을 포함하지만 

   반복 단계의 실행 시간은 제외

 

1) 분할 단계의 세부 사항은 간단하며 

이 단계는 v에 대한 시퀀스의 크기에 비례하여 

시간에 따라 실행된다는 것을 이미 확인했다. 

2) 또한 위에서 설명한 것처럼 

정렬된 두 개의 하위 시퀀스를 병합하는 정복 단계도 

배열이나 연결 리스트를 다루는 것과 무관하게 

선형 시간이 소요된다. 

3) v와 관련된 반복 호출에 의해 처리되는 시퀀스의 크기 = n/2i

노드 v의 깊이: i

노드 v에서 소요되는 시간: O(n/2i)

트리 T를 좀 더 전체적으로 살펴보면, 

그림 11.7과 같이 "노드에서 보낸 시간"의 정의를 고려할 때 

병합 정렬의 실행 시간 = T의 노드에서 보낸 시간의 합

T는 깊이 i에 정확히 2i개의 노드를 가지고 있음을 관찰하라. 

이 간단한 관찰은

깊이 i에서 T의 모든 노드에서 보낸 전체 시간이 O(2i • n/2i) = O(n)임을 의미한다.

 

명제 11.1에 의해 

T의 높이는 ...logn.. T의 각 ...logn... + 1 수준에서 보낸 시간이 O(n)이므로 

다음과 같은 결과를 얻을 수 있다:

제안 11.2: 

알고리즘 병합 정렬은 크기 n의 시퀀스 S를 O(nlogn) 시간에 정렬하며, 

S의 두 요소를 O(1) 시간에 비교할 수 있다고 가정한다.
즉, 병합 정렬 알고리즘은 힙 정렬 알고리즘의 빠른 실행 시간과 점근적으로 일치하다.

그림 11.7:

병합 정렬 트리 T의 시각적 시간 분석.

각 노드는 하위 문제의 크기로 표시된다.

11.1.4 병합 정렬의 Java 구현

이 섹션에서는 병합 정렬 알고리즘의 두 가지 Java 구현을 제시한다. 

하나는 리스트용이고 다른 하나는 배열용이다.

병합 정렬의 재귀적 리스트 기반 구현에 관한 연구

코드 조각 11.3에서는 

정적 재귀적 메소드인 mergeSort로 

리스트 기반 병합 정렬 알고리즘의 완전한 자바 구현을 보여준다. 

comparator(섹션 8.1.2 참조)를 사용하여 두 요소의 상대적 순서를 결정한다.

이 구현에서 입력은 리스트 L이고 보조 리스트 L1과 L2는 재귀적 호출에 의해 처리된다. 

각 리스트는 헤드와 테일 부분에서만 삽입 및 삭제에 의해 수정되므로 

리스트가 이중 연결 리스트로 구현되었다고 가정할 때 

각 리스트 업데이트에는 O(1) 시간이 걸린다(표 6.4 참조). 

저희 코드에서는 보조 리스트에 대해 클래스 NodeList(코드 조각 6.9–6.11)를 사용한다. 

따라서 크기가 n인 리스트 L에 대해 리스트 L이 이중 연결 리스트로 구현되고 

comparator c가 O(n logn) 시간에 L의 두 요소를 비교할 수 있는 경우 

메소드 mergeSort(L,c)는 O(n logn) 시간에 실행된다.

코드 조각 11.3: 

메소드 mergeSort 및 재귀적인 병합 정렬 알고리즘을 구현하는 merge.

/**
 * Sorts the elements of list in nondecreasing order according
 * to comparator C, using the merge-sort algorithm.
 **/
public static <E> void mergeSort (PositionList<E> in, Comparator<E> c) {
  int n = in.size();
  if (n < 2)
    return;  // the in list is already sorted in this case
  // divide
  PositionList<E> in1 = new NodePositionList<E>();
  PositionList<E> in2 = new NodePositionList<E>();
  int i = 0;
  while (i < n/2) {
    in1.addLast(in.remove(in.first())); // move the first n/2 elements to in1
    i++;
  }
  while (!in.isEmpty())
    in2.addLast(in.remove(in.first())); // move the rest to in2
  // recur
  mergeSort(in1,c);
  mergeSort(in2,c);
  // conquer
  merge(in1,in2,c);
}

/**
 * Merges two sorted lists in1 and in2, into a sorted list in.
 **/
 public static <E> void merge (PositionList<E> in1, PositionList<E> in2,
        Comparator<E> c, PositionList<E> in) {
  while (!in1.isEmpty() && !in2.isEmpty())
    if (c.compare(in1.first().element(), in2.first().element()) <= 0)
      in.addLast(in1.remove(in1.first()));
    else
      in.addLast(in2.remove(in2.first()));
  while (!in1.isEmpty()) // move the remaining elements of in1
    in.addLast(in1.remove(in1.first())); 
  while (!in2.isEmpty()) // move the remaining elements of in2
    in.addLast(in2.remove(in2.first())); 
}

병합 정렬의 비재귀적인 배열 기반 구현

O(n log n) 시간 내에 실행되는 비재귀적 버전의 배열 기반 병합 정렬이 있다. 

재귀적 호출 및 노드 생성의 추가 오버헤드를 방지하기 때문에 

실제로는 재귀적 리스트 기반 병합 정렬보다 약간 빠르다.

 

주된 아이디어는

병합 정렬 트리 위로 병합 레벨별로 병합을 수행하는

병합 정렬 바텀업(bottom-up)을 수행하는 것이다. 

요소의 입력 배열이 주어지면

홀짝 쌍의 요소를 모두 길이 2의 정렬된 런(run)으로 병합하는 것으로 시작한다. 

이러한 런을 길이 4의 런으로 병합하고, 

새로운 런을 길이 8의 런으로 병합하여 배열이 정렬될 때까지 수행한다. 

공간 사용을 합리적으로 유지하기 위해 병합된 런을 저장하는 출력 배열을 배치한다. 

 

코드 조각 11.4에서는 자바를 구현하여 

내장된 메소드 System.arraycopy를 사용하여 

두 배열 사이의 셀 범위를 복사한다.

코드 조각 11.4: 비재귀적인 병합 정렬 알고리즘의 구현.

/** Sorts an array with a comparator C using nonrecursive merge sort. */
public static <E> void mergeSort (E[] orig, Comparator<E> c) {
  E[] in = (E[]) new Object[orig.length]; // make a new temporary array
  System.arraycopy(orig,0,in,0,in.length); // copy the input
  E[] out = (E[]) new Object[in.length]; // output array
  E[] temp; // temp array reference used for swapping
  int n = in.length;
  for (int i=1; i < n; i*=2) { // each iteration sorts all length -2*i runs
    for (int j=1; j < n; j+=2*i) { // each iteration merges two length -i pairs
      merge(in,out,c,j,i); // merge from in to out two length -i runs at j
    temp = in; in = out; out = temp; // swamp arrays for next iteration
  }
  // the "in" array contains the sorted array, so re-copy it
  System.arraycopy(in,0,orig,0,in.length);
}
/** Merges two subarrays, specified by a start and increment. */
 protected static <E> void merge (E[] in, E[] out, Comparator<E> c, int start, 
    int inc) { // merge in[start..start+inc-1] and in[start+inc..start+2*inc-1]
  int x = start; // index into run #1
  int end1 = Math.min(start+inc,in.length); // boundary for run #1
  int end2 = Math.min(start+2*inc,in.length); // boundary for run #2
  int y = start+inc; // index into run #2 (could be beyond array boundary)
  int z = start; // index into the out array
  while ((x < end1) && (x < end2))
    if (c.compare(in[x], in[y]) <= 0) out[z++] = in[x++];
    else out[z++] = in[y++];
  if (x < end1) // first run didn't finish
    System.arraycopy(in, x, out , z, end1 - x);
  else if (y < end2) // second run didn't finish
    System.arraycopy(in, y, out , z, end2 - y);
}

11.1.5. 병합 정렬 및 재귀 방정식

병합 정렬 알고리즘의 실행 시간이 O(n log n)임을 정당화하는 다른 방법이 있다(안 11.2). 

즉, 병합 정렬 알고리즘의 재귀적 특성을 보다 직접적으로 다룰 수 있다. 

이 절에서는 병합 정렬의 실행 시간에 대한 이러한 분석을 제시하고, 

이를 통해 재귀 방정식(recurrence equation)

(재귀 관계(reccrrence relation)라고도 함)의 수학적 개념을 소개한다.

함수 t(n): 크기 n의 입력 순서에서 병합 정렬의 최악의 경우 실행 시간

병합 정렬은 재귀적이므로 

함수 t(n)이 재귀적으로 표현되는 방정식을 통해 함수 t(n)을 특성화할 수 있다. 

t(n)의 특성화를 단순화하기 위해 n이 2의 거듭제곱인 경우로 주의를 제한하자. 

(점근적 특성화가 일반적인 경우에도 여전히 유지됨을 보여주는 문제는 연습 문제로 남겨둔다.) 

이 경우 t(n)의 정의를 다음과 같이 지정할 수 있다

 

재귀 방정식(recurrence equation): 함수가 등호의 좌변과 우변에 모두 나타나는 식

비록 이러한 특성화가 정확하고 정확하지만, 

우리가 진정으로 원하는 것은 

함수 t(n) 자체를 포함하지 않는 t(n)의 빅오 형태의 특성화이다. 

즉, 우리는 t(n)의 닫힌 형태(closed-form)의 특성화를 원한다.

n이 상대적으로 크다고 가정할 때, 

재귀 방정식의 정의를 적용함으로써 닫힌 형태의 해를 구할 수 있다. 

예를 들어, 위의 식을 한 번 더 적용한 후, 

t(n)에 대하여 다음과 같이 새로운 재귀를 쓸 수 있다
t(n) = 2(2t(n/(2^2)) + (cn/2)) + cn
       = (2^2)t(n/2^2) + 2(cn/2) + cn = (2^2)t(n/(2^2)) + 2cn.

식을 다시 적용하면 t(n) = (2^3)t(n/(2^3)) + 3cn이 나온다. 

이 시점에서, 우리는 어떤 패턴이 나타나는 것을 봐야 한다. 

그래서 이 식을 적용한 후에 우리는 다음을 얻을 수 있다
t(n) = (2^i)t(n/(2^i)) + icn.

그렇다면 남은 문제는 

이 과정을 언제 중단할 것인가를 결정하는 것이다. 

언제 중단할 것인가를 알아보려면, 

n ≤ 1일 때 닫힌 형태 t(n) = b로 전환해야 하며, 

이는 2i = n일 때 발생한다. 

즉, 이는 i = log n일 때 발생한다. 

이 치환을 사용하면 다음과 같이 산출된다
t(n) = (2^logn )t(n/(2^logn)) + (logn)cn
       = nt(1) + cnlogn
       = nb + cnlogn.

즉, 우리는 t(n)이 O(n logn)라는 사실에 대한 대안적인 정당화를 얻는다.

11.2 퀵 정렬

다음 정렬 알고리즘은 퀵 정렬(quick-sort)이라고 한다. 

이 알고리즘도 병합 정렬과 마찬가지로 

분할정복(divide-and-conquer) 패러다임에 기반을 두고 있지만, 

재귀적 호출 이전에 모든 힘든 작업을 수행하기 때문에 

다소 반대로 이 기법을 사용한다.

퀵 정렬에 대한 높은 수준의 설명

퀵 정렬 알고리즘은 단순 재귀적 접근법을 사용하여 시퀀스 S를 정렬한다. 

주요 아이디어는 분할정복 기법을 적용하는 것인데, 

1) S를 하위 시퀀스로 나누고, 

2) 반복하여 각 하위 시퀀스를 정렬한 다음, 

3) 정렬된 하위 시퀀스를 간단한 연결로 결합하는 것이다. 

특히 퀵 정렬 알고리즘은 다음 세 단계로 구성된다(그림 11.8 참조):

1. 분할(divide): 

S에 적어도 두 개의 원소가 있다면

(S에 0이나 한 개의 원소가 있다면 아무 것도 할 필요가 없음), 

S에서 특정 원소 x를 선택하고, 이것을 피벗(pivot)이라고 한다. 

일반적인 방법처럼 피벗 x를 S의 마지막 원소로 선택한다. 

S에서 모든 원소를 제거하고 세 개의 시퀀스에 넣는다:
• L, 요소를 S에 x보다 작게 저장
• E, S에 원소를 x와 같게 저장하기
• G, 원소를 x보다 큰 S에 저장한다.

물론 S의 원소들이 모두 다른 경우, 

E는 단 하나의 원소, 즉 피벗 자체를 가지고 있다.

2. 반복(recur): 시퀀스 L과 G를 반복적으로 정렬한다.

3. 정복(conquer): 

원소들을 다시 순서대로 S에 집어넣어라. 

1) L의 원소들, 

2) E의 원소들, 

3) G의 원소들을 집어넣어라.

그림 11.8: 퀵 정렬 알고리즘의 시각적 도식.

 

퀵 정렬 트리(quick-sort tree): 퀵 정렬의 실행을 시각화할 수 있는 이진 재귀 트리

퀵 정렬 트리의 각 노드에서 처리되는 입력과 출력 시퀀스를 보여줌으로써 

퀵 정렬 알고리즘의 실행을 요약하면 그림 11.9와 같다. 

퀵 정렬 트리의 단계적 진행을 그림 11.10, 11.11, 11.12와 같다.

그러나 병합 정렬과 달리, 

퀵 정렬의 실행과 관련된 퀵 정렬 트리의 높이는 최악의 경우 선형이다. 

예를 들어, 시퀀스가 n개의 서로 다른 요소로 구성되어 있고 

이미 정렬되어 있는 경우 이러한 현상이 발생한다. 

실제로 이 경우, 피벗을 가장 큰 요소로 선택하면 

크기가 n - 1인 하위시퀀스 L이 생성되는 반면, 

하위시퀀스 E는 크기가 1이고 하위시퀀스 G는 크기가 0이다. 

하위시퀀스 L에서 퀵 정렬이 호출될 때마다 크기가 1만큼 감소한다. 

따라서 퀵 정렬 트리의 높이는 n - 1이다.

그림 11.9: (a) T의 각 노드에서 처리되는 입력 시퀀스; 

(b) T의 각 노드에서 생성되는 

출력 시퀀스 8개의 요소로 구성된 시퀀스에 대한 퀵 정렬 트리 T. 

재귀의 각 레벨에서 사용되는 피벗을 굵은 글씨로 표시했다.

그림 11.10:

퀵 정렬의 시각화 트리의 각 노드 - 재귀적 호출

점선으로 그려진 노드 - 아직 실행되지 않은 호출

굵은 선으로 그려진 노드 - 실행 중인 호출

얇은 선으로 그려진 빈 노드 - 종료된 호출

나머지 노드 - 중단된 호출(즉, 자식 호출이 돌아오기를 기다리는 활성 호출)

(b), (d) 및 (f)에서 수행된 분할 단계를 참고하자(그림 11.11에서 계속)

그림 11.11: 퀵 정렬 실행의 시각화. 

(k)에서 수행된 정복 단계를 참고하자(그림 11.12에서 계속)

그림 11.12: 퀵 정렬 실행의 시각화. 

(p)와 (q) 사이의 호출이 여러 번 생략되었다. 

(o)와 (r)에서 수행된 정복 단계를 참고하자. 

(그림 11.11부터 계속)

배열 및 리스트에 대한 퀵 정렬 수행

코드 조각 11.5에서는 

배열 또는 연결 리스트로 구현된 시퀀스에 

효율적인 퀵 정렬 알고리즘에 대한 의사 코드 설명을 제공한다. 

 

알고리즘은 위에서 설명한 퀵 정렬 템플릿을 따라 

입력된 시퀀스 S를 역방향으로 스캔하여 

피벗보다 작거나 같거나 큰 요소의 리스트 L, E, G로 분할하는 세부 정보를 추가한다. 

 

시퀀스에서 마지막 요소를 제거하는 것은 

시퀀스가 배열로 구현되었는지 연결 리스트으로 구현되었는지에 관계없이 

상수 시간 연산이기 때문에 

이 스캔을 역방향으로 수행한다. 

 

그런 다음 L과 G 리스트를 반복하고 

정렬된 리스트 L, E, G를 다시 S로 복사한다. 

 

시퀀스 끝에 요소를 삽입하는 것은 

시퀀스가 배열로 구현되었는지 연결 리스트로 구현되었는지에 관계없이 

상수 시간 연산이기 때문에 

이 후자의 복사본 세트를 순방향으로 수행한다.

코드 조각 11.5:

연결 리스트 또는 배열로 구현된 입력 시퀀스 S에 대한 퀵 정렬.

Algorithm QuickSort(S):

       Input: A sequence S as an array or linked list

       Output: The sequence S in sorted order

        if S. size() ≤ 1 then 

              return               { S is already sorted in this case}

        p ← S.last().element()              { the pivot}

        Let L, E, and G be empty list-based sequences

        while !S.isEmpty() do      { scan S backwards, dividing it into L, E, and G}

            if S.last().element() < p then 

               L.addLast(S.remove(S.getLast()))

            else if S.last().element() = p then 

               E.addLast(S.remove(S.getLast()))

            else   { the last element in S is greater than p }

               G.addLast(S.remove(S.getLast()))

        QuickSort(L)                 { Recur on the elements less than p }

        QuickSort(G)                 { Recur on the elements greater than p }

        while !L.isEmpty() do   { copy back to S the sorted elements less than p }

            S.addLast(L.remove(L.getFirst()))

        while !E.isEmpty() do   { copy back to S the elements equal to p }

            S.addLast(E.remove(E.getFirst()))

        while !G.isEmpty() do   { copy back to S the sorted elements greater than p }

            S.addLast(G.remove(G.getFirst()))

         return               { S is now in sorted order }

퀵 정렬의 실행 시간

11.1.3절에서 병합 정렬에 사용된 것과 동일한 기법으로 퀵 정렬의 실행 시간을 분석할 수 있다. 

즉, 퀵 정렬 트리 T의 각 노드에서 소요된 시간을 파악하고 모든 노드의 실행 시간을 합산할 수 있다.

코드 조각 11.5를 살펴보면, 

퀵 정렬의 분할 단계와 정복 단계가 선형 시간으로 구현될 수 있음을 알 수 있다. 

따라서 T의 노드 v에서 소요되는 시간은 v의 입력 크기 s(v)에 비례한다.

v의 입력 크기(input size) s(v): 노드 v와 관련된 퀵 정렬의 호출에 의해 처리되는 시퀀스의 크기

하위 E에는 적어도 하나의 요소(피봇)가 있으므로 

v의 자식의 입력 크기의 합은 최대 s(v) - 1이다.

si: 퀵 정렬 트리 T의 깊이 i에 있는 노드들의 입력 크기의 합

분명히 T의 루트 r은 전체 수열과 연관되어 있기 때문에 s0 = n이다. 

또한 피벗은 r의 자식들에게 전파되지 않으므로 s1 ≤ n - 1이다. 

다음 s2를 생각해 보자. 

만약 r의 자식이 입력 크기가 0이 아닌 경우, s2 = n - 3이다. 

그렇지 않으면 (루트의 자식 중 하나는 크기가 0이고, 다른 하나는 크기가 n - 1), s2 = n - 2이다. 

따라서 s2 ≤ n - 2. 

이 추론을 계속하면, 우리는 si ≤ n - i를 얻는다. 

11.2절에서 관찰한 바와 같이, 최악의 경우 T의 높이는 n - 1이다.

따라서, 퀵 정렬의 최악의 실행 시간은, 즉,

=

=

명제 4.3에 의해,

 즉, 퀵 정렬은 O(n^2) 최악의 경우 시간에 실행된다.

이름을 지정하면 퀵 정렬이 빠르게 실행될 것으로 예상할 수 있다. 

그러나 위의 2차 경계는 최악의 경우 퀵 정렬이 느리다는 것을 나타낸다. 

역설적으로 이 최악의 경우는 정렬이 쉬워야 하는 문제 예에서 발생한다. 

만약 순서가 이미 정렬되어 있다면 말이다.

우리의 분석으로 돌아가 보면, 

서로 다른 원소들의 수열에 대한 퀵 정렬에 가장 좋은 경우는 

수열 L과 G가 거의 같은 크기를 가질 때 발생한다는 것을 알 수 있다. 

즉, 가장 좋은 경우에는
s0 = n
s1 = n - 1

s2 = n − (1 + 2) = n − 3
si = n−(1 + 2 + 2^2 + ... + 2^(i−1))=n−(2^i − 1).

따라서 최상의 경우 T는 높이 O(logn)이고 O(nlogn) 시간에 퀵 정렬 실행을 갖는다. 

이 사실의 정당성은 연습(R-11.11)으로 남겨둔다.

퀵 정렬의 예상되는 행동 뒤에 숨겨진 비공식적 직관은 

각 호출에서 피벗이 입력 순서를 거의 균등하게 나눌 것이라는 것이다. 

따라서 평균 실행 시간 퀵 정렬이 

가장 좋은 경우의 실행 시간, 즉 O(nlogn)과 비슷할 것으로 예상한다. 

다음 절에서 무작위화를 도입하면 

퀵 정렬이 정확히 이런 식으로 행동한다는 것을 알게 될 것이다.

11.2.1 랜덤화 퀵 정렬

퀵 정렬을 분석하는 한 가지 일반적인 방법은 

피벗이 항상 순서를 거의 균등하게 나눌 것이라고 가정하는 것이다. 

그러나 우리는 그러한 가정이 일반적으로 사용할 수 없는 입력 분포에 대한 지식을 전제한다고 생각한다. 

예를 들어, 정렬할 "거의" 정렬된 순서가 거의 주어지지 않을 것이라고 가정해야 할 것인데, 

이것은 실제로 많은 응용 분야에서 일반적이다. 

다행히도, 이러한 가정은 우리의 직관을 퀵 정렬의 행동과 일치시키기 위해 필요하지 않다.

일반적으로, 우리는 퀵 정렬을 위한 최적의 실행 시간에 접근하는 방법을 원한다. 

물론, 최적의 실행 시간에 접근하는 방법은 피벗이 입력 순서 S를 거의 균등하게 나누는 것이다. 

만약 이런 결과가 나온다면, 

그 실행 시간은 최적의 실행 시간과 점근적으로 같은 실행 시간이 될 것이다. 

즉, 원소 집합의 "중간"에 가까운 피벗이 있으면

퀵 정렬을 위한 O(nlogn) 실행 시간이 된다.

랜덤으로 피벗 선택

퀵 정렬 방법의 분할 단계의 목표는 수열 S를 거의 균등하게 나누는 것이므로, 

알고리즘에 임의화를 도입하고 입력된 수열의 랜덤 요소(random element)를 피벗으로 선택하자. 

즉, S의 마지막 요소로 피벗을 선택하는 대신 S의 요소를 랜덤으로 피벗으로 선택하고 

나머지 알고리즘은 그대로 유지한다. 

랜덤화 퀵 정렬(randomized quick-sort) :  S의 요소 중 랜덤으로 피벗을 선택한 퀵 정렬

다음 명제는 n개의 요소를 가진 수열에서

랜덤화 퀵 정렬의 예상 실행 시간이 O(nlogn)임을 보여준다.

이 예상은 알고리즘이 내리는 모든 가능한 무작위 선택에 적용되며, 

알고리즘이 부여할 가능성이 있는 입력 시퀀스의 분포에 대한 가정과는 무관하다.

제안 11.3: 크기가 n인 시퀀스 S에서 임의화된 퀵 정렬의 예상 실행 시간은 O(nlogn)이다.

정당화: S의 두 원소를 O(1) 시간으로 비교할 수 있다고 가정한다. 

임의화된 퀵 정렬의 재귀적인 단일 호출을 생각하자.

n:  이 호출에 대한 입력의 크기

선택한 피벗이 하위 L과 G의 크기가 적어도 n/4, 최대 3n/4가 되도록 선택한 경우 이 호출이 "좋음"이고, 

그렇지 않으면 호출이 "나쁨"이다

이제 피벗을 임의로 균일하게 선택할 때 의미하는 바를 생각해 보자. 

임의의 퀵 정렬 알고리즘의 크기 n의 호출에 대하여 

피벗에 대하여 n/2개의 가능한 좋은 선택이 있다는 것을 주목하라. 

따라서 임의의 호출이 양호할 확률은 1/2이다. 

양호한 호출은 적어도 크기 n의 리스트를 크기 3n/4와 n/4의 두 개의 리스트로 분할할 것이고, 

불량 호출은 크기 n - 1의 단일 호출을 생성하는 것만큼 나쁠 수 있다.

이제 임의화된 퀵 정렬에 대한 재귀 추적을 생각해 보자. 

이 추적은 이진 트리 T를 정의하므로 

T의 각 노드는 원래 리스트의 일부분을 정렬하는 부분 문제에 대한 다른 재귀 호출에 대응한다.

만약 (3/4)^(i + 1) * n < (V의 부분 문제의 크기) ≤ (3/4)^i * n 이면 

T의 어떤 노드 v를 크기 그룹(size group) i라고 하자. 

크기 그룹 i의 모든 부분 문제에 대한 기대 시간을 분석해 보자. 

기대의 선형성에 의해 (A.19 명제) 

이 모든 부분 문제에 대한 기대 시간 =  각각의 부분 문제에 대한 기대 시간의 합

이 노드들 중 일부는 양호한 호출에 해당하고 일부는 불량 호출에 해당한다. 

그러나 양호한 호출은 1/2 확률로 발생하므로 

양호한 호출을 받기 전에 연속적으로 수행해야 하는 기대 시간: 2

더욱이, 크기 그룹 i의 한 노드에 양호한 호출이 있는 순간, 

그 노드의 자식들은 i보다 높은 크기 그룹에 속하게 될 것이다. 

따라서, 입력 리스트에 있는 임의의 요소 x에 대하여 

부분 문제에 x를 포함하는 크기 그룹 i의 예상 노드 수: 2

크기 그룹 i의 모든 부분 문제의 예상 크기: 2n이다. 

임의의 부분 문제에 대해 수행하는 비재귀적 작업은 크기에 비례하므로, 

크기 그룹 i의 노드에 대한 전체 기대 시간: O(n)

반복적으로 3/4를 곱하는 것은 반복적으로 4/3을 나누는 것과 같기 때문에 

크기 그룹의 수: log(4/3) n이다. 

크기 그룹의 수: O(log n)

랜덤화 퀵 정렬의 총 예상 실행 시간: O(n log n)(그림 11.13 참조)

그림 11.13: 퀵 정렬 트리 T의 시각적 시간 분석. 

각 노드에는 하위 문제의 크기가 표시된다.

실제로, 랜덤화 퀵 정렬의 실행 시간이 높은 확률로 O(nlogn)임을 보여줄 수 있다.

(연습 C-11.10 참조)

11.2.2 제자리 퀵 정렬

8.3.5절에서 언급한 바와 같이 

객체 자신이 정렬하는 데 필요한 메모리 외에 적은 양의 메모리만을 사용하는 경우에는

정렬 알고리즘이 제자리(in-place)임을 기억하자. 

앞서 설명한 병합 정렬 알고리즘은 제자리 정렬이 아니며, 

제자리 정렬을 수행하려면 11.1.2절에서 설명한 것보다 더 복잡한 병합 메소드가 필요하다. 

그러나 제자리 정렬이 본질적으로 어려운 것은 아니다. 

힙 정렬과 마찬가지로 퀵 정렬도 제자리 정렬에 맞게 조정할 수 있다.

하지만 퀵 정렬 알고리즘을 제자리에서 수행하려면 약간의 독창성이 필요한데, 

모든 재귀 호출에 대한 시퀀스를 저장하기 위해 입력 시퀀스 자체를 사용해야 하기 때문이다. 

코드 조각 11.6에서 제자리 퀵 정렬을 수행하는 PlaceQuickSort의 알고리즘을 보여준다. 

PlaceQuickSort의 알고리즘은 입력 시퀀스 S가 별개의(distinct) 요소의 배열로 제공된다고 가정한다. 

코드 조각 11.6: 입력 배열 S에 대한 제자리 퀵 정렬.

Algorithm inPlaceQuickSort(S,a,b):

       Input: An array S as of distinct elements; integers a and b

       Output: Array S with elements originally from indices from a to b, inclusive,

            sorted in nondecreasing order from indices a to b

        if a ≥ b then return               { at most one element in this case}

        p ← S[b]             { the pivot}

        l ← a             { will scan rightward }

        r ← b - 1             { will scan leftward}

        while l ≤ r do 

            { find an element larger than the pivot }

            while l ≤ r and S[l] ≤ p do 

               l ← l + 1 

            { find an element smaller than the pivot }

            while r ≥ l and S[r] ≥ p do 

               r ← r - 1 

            if l < r then 

               Swap the elements at S[l] and S[r]

        { put the pivot into its final place }

        Swap the elements at S[l] and S[b]

        { recursive calls }

        inPlaceQuickSort(S,a,l - 1)

        inPlaceQuickSort(S,l - 1,b)

        { we are done at this point, since the sorted subarrays are already consecutive }

제자리 퀵 정렬은 요소 스와핑을 사용하여 입력 시퀀스를 수정하고

명시적으로 서브 시퀀스를 만들지 않다. 

실제로 입력 시퀀스의 서브 시퀀스는 

암시적으로 왼쪽 인덱스 l과 오른쪽 인덱스 r로 지정된 위치 범위로 표시된다. 

 

분할 단계는 그림 11.14와 같이 순서가 반대인 요소의 쌍을 스와핑하면서 

배열을 l 앞에서 r 뒤로 동시에 스캔하여 수행한다. 

이 두 인덱스가 "만날" 때, 서브 배열 L과 G는 만남의 점의 반대쪽에 있다. 

알고리즘은 이 두 서브 배열에서 반복하여 완성된다.

제자리 퀵 정렬은 새로운 시퀀스의 생성과 요소 간의 이동이 

일정한 요인에 의해 발생하는 실행 시간을 줄인다. 

코드 조각 11.7에서 Java 버전의 제자리 퀵 정렬을 보여준다.

그림 11.14: 제자리에서 퀵 정렬 단계를 분할한다. 

인덱스 l은 왼쪽에서 오른쪽으로 순서를 스캔하고 

인덱스 r은 오른쪽에서 왼쪽으로 순서를 스캔한다. 

스왑은 l이 피벗보다 큰 요소에 있고 r이 피벗보다 작은 요소에 있을 때 수행된다. 

피벗과의 최종 스왑을 통해 분할 단계가 완료된다.

코드 조각 11.7: 별개의 요소를 가정한 제자리 퀵 정렬 코딩.

public static <E> void quickSort (E[] s, Comparator<E> c) {
  if (s.length < 2) return; // the array is already sorted in this case
  quickSortStep(s, c, 0, s.length-1); // recursive sort method
}
public static <E> void quickSortStep (E[] s, Comparator<E> c,
                        int leftBound, int rightBound ) {
  if (leftBound >= rightBound) return; // the indices have crossed
  E temp; // temp object used for swapping
  E pivot = s[rightBound];
  int leftIndex = leftBound;     // will scan rightward
  int rightIndex = rightBound-1;     // will scan leftward
  while (leftIndex <= rightIndex) { // scan right until larger than the pivot
    while ((leftIndex <= rightIndex) && c.compare(s[leftIndex], pivot)<=0))
      leftIndex++;
    // scan leftward to find an element smaller than the pivot
    while ((rightIndex >= leftIndex) && c.compare(s[rightIndex], pivot)<=0))
      rightIndex--;
    if (leftIndex < rightIndex) { // both elements were found
      temp = s[rightIndex];
      s[rightIndex] = s[leftIndex]; // swap these elements
      s[leftIndex] = temp;
    }
  } // the loop continues until the indices cross
  temp = s[righttBound]; // swap pivot with the element at leftIndex
  s[rightBound] = s[leftIndex];
  s[leftIndex] = temp; // the pivot is now at leftIndex, so recurse
  quickSortStep (s, c, leftBound, leftIndex-1);
  quickSortStep (s, c, leftIndex+1, rightBound);
}

안타깝게도 위의 구현은 제자리가 보장되지 않는다. 

섹션 14.1.1을 참조하면, 

재귀 트리의 깊이에 비례하는 스택을 위한 공간이 필요하며, 이 경우 n - 1만큼 클 수 있다. 

물론 예상되는 스택 깊이는 O(logn)이며, 이는 n에 비해 작다. 

그럼에도 불구하고 간단한 트릭을 사용하면 스택 크기가 O(logn)임을 보장할 수 있다.

 

주요 아이디어는 명시적 스택을 사용하여 

재귀적이지 않은 버전의 퀵 정렬을 설계하여 

서브 문제를 반복적으로 처리하는 것이다.

 

(각각 서브 배열 경계를 표시하는 인덱스 쌍으로 나타낼 수 있음)

각 반복에는 상단 서브 문제를 터뜨리고, 

(충분히 큰 경우) 두 개로 분할한 다음 

두 개의 새로운 서브 문제를 푸시하는 것이 포함된다. 

비결은 새로운 서브 문제를 푸시할 때 

먼저 큰 서브 문제를 푸시하고, 다음에 작은 서브 문제를 푸시해야 한다는 것이다. 

 

이러한 방식으로, 서브 문제의 크기는 스택을 내려갈 때 최소 두 배 이상 증가하므로 

스택은 최대 O(logn)의 깊이를 가질 수 있다.