미래를 예측하는 최고의 방법은 그걸 만드는 것이다.

The best way to predict the future is to invent it.

— 앨런 케이Alan Kay (1971)

데이터가 모였을 때 그 분포가 궁금한 경우가 있습니다. 대표적인 방법으로는 중간값median, 즉 순서대로 놓았을 때 50%에 위치하는 데이터를 보는 것입니다. 또는 75%의 경우와 같은 사분위수quartile나 99%와 같이 극단적인 경우도 관심이 대상이 될 수 있습니다.

이런 문제들은 일반화해서 $k$ 번째로 작은 데이터, 즉 순서 통계량order statistics을 찾는 것으로 바라볼 수 있습니다.

order statistics diagram — 그림 1. 중간값과 순서 통계량 예시. 그림처럼 모인 공들 중에 2가 첫 번째, 6이 중간값이 됩니다.

간단한 해결법은 데이터를 소트하는 것입니다. 그러면 모든 데이터의 순위를 구하게 되지만, 이전 글에서도 다뤘던 머지 소트merge sort 같은 비교 기반 소팅 알고리즘은 적어도 $\Omega(n \lg n)$ 의 시간이 듭니다. 하지만 하나의 데이터의 순위만 필요하다면, 대체로 $\Theta(n)$ 의 시간이 드는 퀵셀렉트quickselect 알고리즘이 대안이 될 수 있습니다.

퀵셀렉트는 $k$ 번째 데이터를 바이너리 서치처럼 서치 구간을 줄여가며 찾습니다. 예를 들어, 숫자가 적힌 공이 아무렇게나 섞여 있고, 중간값인 숫자가 궁금하다고 해봅시다.

quickselect diagram — 그림 2. 중간값을 찾는 퀵셀렉트. 처음에는 5를 피벗으로 골라 두 부분으로 나누고, 피벗 이하인 숫자를 버립니다. 그 다음 6을 피벗으로 고르면, 나머지가 세 개가 6보다 크기 때문에 6이 중간값이라는 것을 알게됩니다.

여기서 가장 왼쪽을 피벗pivot이라는 이름으로 고르고, 나머지를 피벗 이하와 이상인 두 부분으로 분리합니다. 그리고 피벗을 그 사이에 두면, 피벗은 소트된 위치에 오게 됩니다. 따라서 피벗이 중간값인지 아닌지 알 수 있게 됩니다.

피벗이 중간값이면, 답을 구한 것입니다. 반면 중간값이 아니면, 나눈 한쪽은 볼 필요가 없다는 뜻이기도 하므로 피벗과 함께 버립니다. 이 과정을 반복하면 중간값을 찾게 됩니다.

이 아이디어를 수도코드로 표현한다면 다음과 같습니다. 데이터가 배열 $\textit{arr}$ 로 주어졌을 때, $k$ 번째로 작은 데이터를 찾습니다. (여기서 $k$ 는 $0$ 부터 시작한다고 하면, 일반적인 의미의 $k$ 번째와는 다르겠지만 어쨌든 이런 표현을 쓰겠습니다. 정확히 말하면, 소트했을 때 배열에서 인덱스가 $k$ 일 데이터를 찾는 것입니다.)

퀵셀렉트 ( $\textit{arr}$ , $k$ ) // $\textit{arr}$ 에서 $\textit{k}$ 번째로 작은 데이터를 구함

[ $\textit{begin}$ , $\textit{end}$ ) $\leftarrow$ [ $0$ , $\textit{arr}$ 의 크기) // 서치 구간을 초기화

다음을 $\textit{begin} < \textit{end}\,$ 인 동안 반복 // 서치 구간이 비어있지 않은 동안

// 파티셔닝: 피벗 $\textit{arr}$ [ $i$ ]를 기준으로 서치 구간을 둘로 나눔

// [ $\textit{begin}$ , $\textit{i}$ )의 데이터는 피벗 이하, [ $\textit{i+1}$ , $\textit{end}$ )는 피벗 이상

// 이후 $\textit{arr}$ [ $i$ ]는 소트된 위치에 있음

$i \leftarrow$ 파티셔닝( $\textit{arr}$ , $\textit{begin}$ , $\textit{end}$ )

// $k$ 번째 데이터를 찾으면 리턴

만약

i = k

이면

반복 중단

// 찾지 못했으면

만약 $i < k$ 이면 // $i$ 번째 데이터가 $k$ 번째보다 작으면

// [ $\textit{begin}$ , $i+1$ )은 $k$ 번째 데이터보다 작으므로 서치 구간에서 제외

$\textit{begin} \leftarrow i+1$

아니면 // $i$ 번째 데이터가 $k$ 번째보다 크면

// [ $i$ , $\textit{end}$ )는 $k$ 번째 데이터보다 크므로 제외

$\textit{end} \leftarrow i$

리턴

\textit{arr}

[

k

]

여기서 구간 [ $a$ , $b$ )는 $a$ 는 포함하고 $b$ 는 제외한, $a$ 부터 $b$ 까지의 구간을 말합니다.

퀵셀렉트가 의존하는 파티셔닝 알고리즘은 세 가지를 맡습니다.

피벗을 골라서, 전체를 피벗 이하와 이상인 두 부분, [ $\textit{begin}$ , $i$ )와 [ $i+1$ , $\textit{end}$ )으로 나눕니다.
피벗의 인덱스 $i$ 를 구합니다.
피벗을 소트된 위치 $\textit{arr}$ [ $i$ ]에 둡니다. (첫 번째 작업을 수행하면 자연스럽게 따라오는 효과입니다.)

partitioning diagram — 그림 3. 파티셔닝 다이어그램. 입력 값으로 들어온 배열에서, 피벗을 기준으로 두 구간으로 나눕니다.

퀵셀렉트의 시간 복잡도 $T_s$ 는, 파티셔닝 알고리즘이 피벗을 중간값에 가깝게 고를 수록 작아집니다. 뒤에서 볼 것처럼, 파티셔닝 알고리즘의 시간 복잡도 $T_p$ 는 데이터의 개수 $m$ 과 상수 $c$ 에 대해 $T_p(m) \sim cm$ 이 됩니다. 이를 이용해, $n$ 개의 데이터에서 마지막 순위를 찾을 때, 퀵셀렉트에 드는 시간 $T_s$ 를 구해봅시다.

피벗을 항상 중간값으로 고를 때: 퀵셀렉트의 서치 구간이 바이너리 서치처럼 절반씩 줄어듭니다. 따라서 파티셔닝은 대략 $n, n/2, n/4, \dots, 1$ 개의 데이터를 받으므로, 다음과 같이 $T_s(n) = \Theta(n)$ 를 얻습니다.
$\begin{align*} T_s(n) &= T_p(n) + T_p(n/2) + T_p(n/4) + \dots + T_p(1) \\ &\sim 2cn = \Theta(n) \end{align*}$
피벗을 항상 최소값이나 최대값으로 고를 때: 오직 피벗 하나만 서치 구간에서 제외되므로, 서치 구간은 하나씩 줄어듭니다. 따라서 파티셔닝은 $n, n-1, n-2, \dots, 1$ 개의 데이터를 받으므로, $T_s(n) = \Theta(n^2)$ 를 얻습니다.
$\begin{align*} T_s(n) &= T_p(n) + T_p(n-1) + T_p(n-2) + \dots + T_p(1) \\ &\sim cn^2 = \Theta(n^2) \end{align*}$

이처럼 퀵셀렉트의 시간 복잡도 $T_s$ 는 피벗에 따라 결정됩니다. 그런데 파티셔닝 알고리즘이 피벗을 고르는 위치가 정해져있다면, 이는 입력 값에서 이미 결정되므로, $T_s$ 또한 입력 값에 따라 달라집니다. 이것이 시간 복잡도를 계산할 때, 최선 또는 최악의 경우 같은 특별한 종류의 입력 값을 가정하는 이유입니다.

그런데 시간 복잡도가 입력 값에 영향을 받지 않도록 설계할 수도 있습니다. 예를 들어, 퀵셀렉트 알고리즘에서 맨 처음에 입력 값을 섞는다면, 최악의 경우나 최선의 경우의 입력 값은 존재하지 않게 됩니다. 다시 말해, 퀵셀렉트를 고의로 빠르게 또는 느리게 만들 수는 없게 됩니다. 이처럼 무작위적인 요소에 의존하는 알고리즘을 랜더마이즈드 알고리즘randomized algorithm이라고 부릅니다.

따라서 랜더마이즈드 알고리즘의 시간 복잡도는 최선의 경우나 최악의 경우 말고, 확률적인 기대값expected value 혹은 기대 수행 시간expected running time으로 계산합니다. 사실 앞에서 퀵셀렉트가 대체로 $\Theta(n)$ 의 시간이 든다고 한 것은 그 기대값이 $\Theta(n)$ 이라는 의미입니다.

dice — 그림 4. 무작위적인 요소를 알고리즘에 사용하면, 알고리즘의 수행 시간이 입력 값에 따라 달라지지 않도록 만들 수 있습니다. — 사진: Alois Komenda

이런 알고리즘의 장점은, 입력 값의 분포를 예상하고 가정해야 하는 대신, 그 분포 자체를 알고리즘에서 만들어낸다는 것입니다. 즉 알고리즘을 느리게 만드는 가능성은 더 이상 알고리즘 외부에 존재하지 않고, 대신 알고리즘 내부에서 만들어내는 것이 됩니다. 예를 들어, 앞서 본 퀵셀렉트 알고리즘을 랜더마이즈드 알고리즘으로 바꾸면, 입력 값의 분포에 상관없이 똑같은 기대 수행 시간으로 소요 시간을 예측할 수 있게 됩니다.

여기서는 앞서 본 퀵셀렉트와 파티셔닝을 랜더마이즈드 알고리즘으로 만들어보겠습니다. 한편, 파티셔닝은 적어도 피벗은 소트한다는 특징이 있는데요. 각 데이터를 한 번씩 피벗으로 선택한다면 모두 소트한 게 되고, 이 아이디어로 퀵소트quicksort라고 불리는 소팅 알고리즘을 만들 수 있습니다. 또한 파티셔닝에는 두 부분 대신 세 부분으로 나누는 방법도 있습니다. 이것은 중복된 데이터가 많은 경우 퀵소트를 더 빠르게 만드는 요소가 됩니다.

그러면 이 퀵셀렉트와 퀵소트를 다른 라이브러리의 도움 없이 자바Java로 만들어보겠습니다.

랜더마이즈드 파티셔닝

예를 들어, 아무렇게나 섞인 카드에서 가장 왼쪽 카드를 피벗으로 골랐다고 해봅시다. 그러면 파티셔닝 알고리즘은 나머지 카드를 두 부분으로 나눠야 합니다.

partitioning — 그림 5. 파티셔닝 예시. 빈 두 구간으로 시작해, 왼쪽 구간은 피벗 이하인 카드를, 오른쪽은 피벗 이상인 카드를 채워넣습니다. 이후 가운데 영역에 카드가 남아있으면, 이 영역의 양쪽 카드를 스왑하고 각 구간을 하나씩 늘립니다. 이를 반복하면 파티셔닝이 끝납니다.

나머지 카드 양쪽 끝에 가상의 빈 구간이 있다고 해봅시다. 여기에 카드를 두 부분으로 나눌 것입니다. 그러면 피벗 이하인 구간은 [ $b$ , $l$ ), 이상인 구간은 [ $u$ , $e$ )로 표현할 수 있습니다. 파티션 구간에 속하지 않은 카드는 [ $l$ , $u$ ) 구간에 속합니다.

파티셔닝 알고리즘은 $l$ 위치의 카드가 피벗보다 작을 때마다 $l$ 을 하나씩 늘립니다. 이는 피벗 이하 구간 [ $b$ , $l$ )을 하나씩 늘리는 것입니다. 반대로, $u-1$ 위치의 카드가 피벗보다 클 때마다 $u$ 를 하나씩 줄입니다.

이렇게 했는데 $l < u$ 이라면 파티셔닝이 끝나지 않은 것입니다. 왜냐면 $l < u$ 은 구간 [ $l$ , $u$ )가 비어있지 않다는 뜻이고, 이 구간은 아직 어느 파티션 구간에 속하지 않은 것이기 때문입니다. 이를 해소하기 위해서, $l$ 과 $u-1$ 위치의 카드를 서로 바꿔 올바른 파티션 구간에 포함시킵니다. 그리고 이 과정을 반복합니다.

이 방법은 퀵소트를 만들었던 토니 호어Tony Hoare가 생각해냈기 때문에 호어Hoare 파티션이라고도 불립니다.

파티셔닝

호어 파티션을 수도코드로 표현하면 이렇습니다.

파티셔닝 ( $\textit{arr}$ , $\textit{begin}$ , $\textit{end}$ ) // $\textit{arr}$ 의 구간 [ $\textit{begin}$ , $\textit{end}$ )을 두 부분으로 나눔

// 첫 번째 위치를 피벗으로 선택

$\textit{pivot} \leftarrow$ $\textit{arr}$ [ $\textit{begin}$ ]

// 구간 [ $\textit{begin}+1$ , $l$ )은 피벗 이하가 속함

$l \leftarrow \textit{begin}+1$

// 구간 [ $u$ , $end$ )는 피벗 이상이 속함

$u \leftarrow \textit{end}$

다음을 항상 반복

// 피벗 이하인 구간 [ $\textit{begin}+1$ , $l$ )을 늘림

다음을

l < \textit{end}\,

이고

\textit{arr}

[

l

]

< \textit{pivot}

인 동안 반복

$l \leftarrow l + 1$

// 피벗 이상인 구간 [ $u$ , $\textit{end}$ )를 늘림

다음을

\textit{arr}

[

u-1

]

> \textit{pivot}

인 동안 반복

$u \leftarrow u - 1$

만약 $l < u$ 이면 // 파티셔닝이 끝나지 않았다면

$\textit{arr}$ [ $l$ ]과 $\textit{arr}$ [ $u-1$ ] 스왑

$l \leftarrow l + 1$

$u \leftarrow u - 1$

아니면 // 파티셔닝이 끝났다면

$\textit{arr}$ [ $\textit{begin}$ ]과 $\textit{arr}$ [ $u-1$ ] 스왑

리턴

u-1

시간 복잡도를 수행하는 수도코드 줄의 개수라고 합시다. 반복문에서 파티션 구간을 늘리는 부분에 $T_1$ , $l < u$ 라서 수행하는 부분에 $T_2$ 의 시간이 든다고 해봅시다. 반복문이 끝날 때 두 줄의 코드를 더 수행하므로, 반복문은 총 $T_1 + T_2 + 2$ 의 시간을 가집니다.

구간의 길이가 $n$ 일 때, $T_1$ , $T_2$ 는 다음과 같습니다.

$T_1$ : 모든 데이터를 구간에 포함시켜야 반복문이 끝나므로, $n$ 번 반복합니다. 여기에 네 줄의 코드가 있으므로 $T_1(n) = 4n$ 입니다.
$T_2$ : 데이터가 소트된 경우, $l < u$ 인 경우는 일어나지 않으므로 $T_2(n) = 0$ 입니다. 데이터가 반대로 소트된 경우, 양쪽 구간은 오직 여기서만 한 칸씩 늘어나므로, 대략 $n/2$ 번 반복합니다. 여기에 네 줄의 코드가 있으므로 $T_2(n) = 2n$ 입니다.

파티셔닝 알고리즘은 세 줄의 코드와 반복문을 가지므로, 다음과 같이 $T_p(n)$ 의 범위를 얻습니다.

4n + 5 \leq T_p = 3 + (T_1 + T_2 + 2) \leq 6n + 5

따라서 $T_p(n) = \Theta(n)$ 이 됩니다.

랜더마이즈드 파티셔닝

피벗을 모든 데이터 중에 무작위로 고르는 랜더마이즈드 파티셔닝을 만들어봅시다. 이는 무작위로 고른 피벗을 첫 번째 위치로 옮기고, 기존 파티셔닝을 리턴하는 것으로 간단히 만들 수 있습니다.

랜더마이즈드 파티셔닝 ( $\textit{arr}$ , $\textit{begin}$ , $\textit{end}$ ) // $\textit{arr}$ 의 구간 [ $\textit{begin}$ , $\textit{end}$ )을 두 부분으로 나눔

// 피벗의 인덱스로 무작위 숫자를 선택

$i \leftarrow$ [ $\textit{begin}$ , $\textit{end}$ ) 중 무작위 숫자

// 피벗을 $\textit{begin}$ 위치로 옮김

$\textit{arr}$ [ $\textit{begin}$ ]과 $\textit{arr}$ [ $\textit{i}$ ] 스왑

// $\textit{begin}$ 위치를 피벗으로 하는 기존 파티셔닝 사용

리턴 파티셔닝(

\textit{arr}

\textit{begin}

\textit{end}

)

이 알고리즘의 시간 복잡도 $T_{rp}(n)$ 은 기존 파티셔닝에서 두 줄의 수도코드를 더 수행하므로 $T_p(n) + 2$ 가 됩니다. 따라서 다음 범위를 얻습니다.

4n + 7 \leq T_{rp}(n) \leq 6n + 7

그리고 $T_{rp}(n) = \Theta(n)$ 이 됩니다.

구현하기

파티셔닝 알고리즘을 스트레터지 패턴으로 만들어보겠습니다. 이를 위해 먼저 스트레터지의 인터페이스를 만듭시다.

public interface PartitionStrategy<T> {
  public int partition(T[] arr, int begin, int end, Comparator<T> comp);
}

이 메소드는 arr 배열의 [begin, end) 구간을 두 구간으로 나눕니다. 여기서 comp는 피벗과 대소 비교를 위해 쓰입니다.

이제 처음에 언급했던, 한 쪽의 데이터를 피벗으로 하는 파티셔닝을 스트레터지로 구현합니다. 이는 수도코드를 그대로 옮긴 것입니다.

public class TwoWayStrategy<T> implements PartitionStrategy<T> {
  public int partition(T[] arr, int begin, int end, Comparator<T> comp) {
    assert begin >= 0;
    assert end > begin;
    assert arr.length >= end;

    T pivot = arr[begin];

    int l = begin+1;
    int u = end;

    while (true) {
      while (l < end && isLessThan(arr[l], pivot, comp)) {
        l++;
      }
      while (isGreaterThan(arr[u-1], pivot, comp)) {
        u--;
      }

      if (l < u) {
        swap(arr, l, u-1);
        l++;
        u--;
      } else {
        // move pivot (at `begin`) to `u-1` and return it
        swap(arr, begin, u-1);
        return u-1;
      }
    }
  }
}

랜더마이즈드 파티셔닝은 수도코드에서처럼 무작위 숫자에 의존합니다. 이 부분을 외부에서 rand 파라미터로 받도록 다음과 같은 생성자를 만듭시다.

public class RandTwoWayStrategy<T> implements PartitionStrategy<T> {
  IntBinaryOperator rand;

  public RandTwoWayStrategy(IntBinaryOperator rand) {
    this.rand = rand;
  }

  // ...

자바에서 제공하는 IntBinaryOperator 인터페이스는 두 숫자를 받아 하나의 숫자를 내놓는 함수입니다. 여기서는 예를 들어 3부터 10까지 중 무작위 숫자처럼, 구간으로서 두 숫자로 받아 무작위 숫자를 주는 함수로서 사용할 것입니다.

이렇게 무작위 숫자를 알고리즘 바깥에서 결정하면 테스트하기 쉬운 코드가 됩니다. 왜냐면 무작위 숫자를 항상 똑같이 결정할 수 있기 때문입니다.

이어서 랜더마이즈드 파티셔닝을 구현해봅시다. 이는 수도코드를 그대로 옮긴 것입니다.

  public int partition(T[] arr, int begin, int end, Comparator<T> comp) {
    // select a random number
    int pivotIndex = this.rand.applyAsInt(begin, end);

    swap(arr, begin, pivotIndex);

    PartitionStrategy<T> strat = new TwoWayStrategy<>();
    return strat.partition(arr, begin, end, comp);
  }

이는 자바의 Random 클래스를 통해, 무작위 숫자를 선택하는 파티셔닝을 수행할 수 있습니다.

PartitionStrategy<Integer> strat = new RandTwoWayStrategy<>(new Random()::nextInt);

이제 유닛 테스트를 작성해봅시다. 여기서는 JUnit 5 프레임워크를 이용합니다. 아래 테스트 케이스는 첫 번째 숫자인 4를 피벗으로 고르고, 배열을 피벗 이하와 이상인 두 부분으로 나누기를 기대합니다. chooseBegin가 구간의 첫 번째 숫자를 고르기 때문에, 무작위 숫자 대신 항상 4를 피벗으로 고를 수 있습니다.

  @Test
  public void testSuccess() {
    Integer[] arr = new Integer[] { 4, 5, 6, 2, 3 };
    Comparator<Integer> identity = Comparator.comparing(v -> v);

    IntBinaryOperator chooseBegin = (begin, end) -> begin;
    PartitionStrategy<Integer> strat = new RandTwoWayStrategy<>(chooseBegin);

    int pivot = strat.partition(arr, 0, arr.length, identity);
    int pivotVal = arr[pivot];

    assertEquals(4, pivotVal);
    assertTrue(Arrays.stream(arr, 0, pivot).allMatch(v -> v <= pivotVal));
    assertTrue(Arrays.stream(arr, pivot+1, arr.length).allMatch(v -> v >= pivotVal));
  }

이는 잘 통과하는 테스트가 됩니다.

랜더마이즈드 퀵셀렉트

랜더마이즈드 파티셔닝으로 퀵셀렉트를 만들면, 이 또한 랜더마이즈드 알고리즘이 됩니다. 그리고 이것은 처음에 봤던 퀵셀렉트 수도코드에서, 파티셔닝을 단순히 랜더마이즈드 알고리즘으로 바꾸면 됩니다.

앞으로 만들 랜더마이즈드 퀵셀렉트에서는 모든 데이터가 피벗이 될 확률이 똑같다고 가정할 것입니다. 이로부터 시간 복잡도의 확률적인 기댓값을 구할 수 있는데요. 이를 시간 복잡도의 확률적 분석probabilistic analysis라고도 부릅니다.

그러면 기대 수행 시간을 구해보고, 이를 자바로 구현해 실제 소요 시간을 측정해보겠습니다.

확률과 기댓값

시간 복잡도를 계산하기 전에, 앞으로 사용할 확률론probability theory의 내용을 간단히 짚어보겠습니다.

샘플 스페이스sample space는 (우연히) 일어날 수 있는 결과, 혹은 아웃컴outcome을 모은 집합set입니다.

예를 들어, 동전 던지기의 샘플 스페이스는 앞면 $H$ , 뒷면 $T$ , 세워진 옆면 $S$ 를 모은 집합 $\{H, T, S\}$ 로 만들 수 있습니다.
사건 또는 이벤트란event란 샘플 스페이스의 부분 집합을 말하고, 확률probability이란 이벤트마다 숫자를 할당한 것입니다. 확률은 항상 $0$ 이상 $1$ 이하의 범위를 가집니다.

이벤트 $A$ 가 일어날 확률을 $P(A)$ 로 표현합시다. 예를 들어, 앞면이 나올 확률은 $P(H)$ 입니다. 그리고 앞면이 나오거나 뒷면이 나올 확률은 $P(H \cup T)$ 이 되고, 이 둘은 동시에 일어날 수 없으므로 $P(H)+P(T)$ 으로 정의됩니다.
랜덤 변수random variable란 샘플 스페이스의 아웃컴마다 숫자를 할당한 것입니다.

예를 들어, 앞면 $H$ 일때만 $1$ 이고 나머지 경우는 $0$ 으로 랜덤 변수 $I$ 를 정의합시다.
$I = \begin{cases} 1 \quad (H) \\ 0 \quad (\textrm{otherwise}) \end{cases}$
그러면 $I$ 가 $1$ 일 확률은 $P(I=1)$ 로 표현합니다. (그리고 이 경우 $P(H)$ 와 같습니다.) 이렇게 하나의 아웃컴에 대해서 $1$ 이 할당된 랜덤 변수를 인디케이터indicator라고 부릅니다.
랜덤 변수 $X$ 의 기댓값expected value $E[X]$ 는 각 $X$ 의 값과 그 확률 곱한 것들의 합, 즉 $\sum_{x} x P(X=x)$ 입니다.

예를 들어, 방금의 예시에서 정의한 인디케이터 $I$ 의 기댓값 $E[I]$ 는 다음과 같이 $P(H)$ 와 같습니다.
$\begin{align*} E[I] &= \sum_{x} xP(I=x) \\ &= 1P(I=1) + 0P(I=0) \\ &= P(I=1) \\ &= P(H) \end{align*}$
사실 어떤 아웃컴 $A$ 에 대해 $1$ 이 할당된 인디케이터 $X$ 는 그 기댓값 $E[X]$ 가 항상 확률 $P(A)$ 와 같습니다.
기댓값의 특징으로, 증명은 생략하겠지만, $E[X+Y]=E[X]+E[Y]$ 이 항상 성립하고, 랜덤 변수가 독립independent이면 $E[XY]=E[X]E[Y]$ 이 성립합니다. 여기서 독립이란 한 쪽의 결과가 다른 결과가 나오는 데 영향을 미치지 않는 것을 말합니다.

시간 복잡도

그러면 랜더마이즈드 퀵셀렉트에서 반복문의 기대 수행 시간 $E[T_{rs}]$ 를 구해봅시다. 수도코드는 기존 퀵셀렉트의 수도코드와 다른 게 없으므로, 이를 바탕으로 진행합니다.

$k$ 번째 데이터를 찾는다고 하고, 피벗을 $i$ 번째 데이터로 골랐다고 해봅시다. 퀵셀렉트의 반복문은, 피벗이 $k$ 번째 데이터보다 작다면, $n$ 개의 데이터를 $n-i-1$ 개로 줄이고, 반대의 경우, $i$ 개로 줄입니다. 그리고 파티셔닝 이후, 구간을 줄이는 데 두 줄의 코드를 더 수행합니다. 따라서 $T_{rs}$ 는 랜덤 변수로서 이렇게 표현할 수 있습니다.

T_{rs}(n) = T_{rp}(n) + \sum_{i=0}^{k-1} I_i T_{rs}(n-i-1) + \sum_{i=k+1}^{n-1} I_i T_{rs}(i) + 2

그런데 모든 데이터가 똑같은 확률로 피벗이 되므로, $E[I_i] = 1/n$ 입니다. 이로부터 시간 복잡도의 기댓값을 얻습니다.

\begin{align*} \tag{Eq.1} E[T_{rs}(n)] &= T_{rp}(n) + \frac{1}{n} \!\left( \sum_{i=0}^{k-1} E[T_{rs}(n-i-1)] + \sum_{i=k+1}^{n-1} E[T_{rs}(i)] \right) + 2 \end{align*}

이제 다음과 같은 범위를 구해서 $E[T_{rs}(n)] = \Theta(n)$ 라는 결론을 보일 것입니다.

\begin{align*} 4n + 9 \leq E[T_{rs}(n)] < cn \end{align*}

여기서 $c$ 는 앞으로 정할 상수입니다.

첫 번째로, $E[T_{rs}(n)] \geq 4n + 9$ 는 $E[T_{rs}(n)] \geq T_{rp}(n) + 2$ 로부터 나옵니다. 이는 $\textrm{Eq.1}$ 에서 괄호 부분을 없애서 얻을 수 있습니다.

두 번째로, $E[T_{rs}(n)] < cn$ 은 다음과 같이 귀납법induction으로 보일 수 있습니다. 먼저, 이 식이 $m < n$ 인 $m$ 에 대해 성립한다고 해봅시다. 그러면 다음을 얻습니다.

\begin{align*} E[T_{rs}(n)] &< ( 6n + 9 ) + \frac{1}{n} \!\left( \sum_{i=0}^{k-1} c(n-i-1) + \sum_{i=k+1}^{n-1} ci \right) \\ &= ( 6n + 9 ) + \underbrace{\frac{c}{2n} \!\left( 2kn - 2k - 2k^2 + n^2 - n \right)}_{\small\textrm{max when }k=(n-1)/2} \\ \end{align*}

마지막 줄에서는 미분과 같은 방법으로, $k = (n-1)/2$ 일 때가 최대임을 알 수 있습니다. 즉 중간값을 찾을 때 가장 느린 것입니다. 여기서 $c \geq 24$ 로 선택하면, 다음과 같이 보이고자 하는 바를 얻습니다.

\begin{align*} E[T_{rs}(n)] &< \left( 6 + \frac{3}{4}c \right)n + \left( 9 - c + \frac{c}{4n} \right) \\ &< cn + 0 \end{align*}

$c \geq 24$ 이면 왼쪽 괄호는 $cn$ 이하이고, 두 번째 괄호는 $0$ 보다 작기 때문입니다.

자바로 구현하기

다음과 같이 수도코드를 그대로 옮겨 퀵셀렉트를 구현해봅시다. 여기서 파티셔닝은 외부에서 주입받으므로, 이것이 랜더마이즈드 알고리즘인지 아닌지는 신경쓰지 않습니다.

public class QuickSelectArray {
  public static <T> T select(T[] arr, int target, PartitionStrategy<T> strat, Comparator<T> comp) {
    int begin = 0;
    int end = arr.length;

    while (begin < end) {
      int pivot = strat.partition(arr, begin, end, comp);

      if (pivot == target) {
        break;
      }

      if (pivot < target) {
        begin = pivot + 1;
      } else {
        end = pivot;
      }
    }

    return arr[target];
  }

  // ...
}

comp 파라미터를 생략할 수 있도록 다음과 같이 오버로딩합니다.

  public static <T extends Comparable<? super T>> T select(T[] arr, int target, PartitionStrategy<T> strat) {
    Comparator<T> identityComp = Comparator.comparing(v -> v);

    return QuickSelectArray.select(arr, target, strat, identityComp);
  }

유닛 테스트로 잘 동작하는지 확인해봅시다. 다음 케이스는 다섯 개의 숫자 중에서 두 번째로 작은 숫자를 찾습니다.

  @Test
  public void testSuccess() {
    Integer[] arr = new Integer[] { 5, 4, 3, 2, 1 };

    IntBinaryOperator chooseMid = (begin, end) -> begin + (end-begin)/2;
    PartitionStrategy<Integer> strat = new RandTwoWayStrategy<Integer>(chooseMid);

    int selected = select(arr, 1, strat);

    assertEquals(2, selected);
  }

여기서 chooseMid는 파티셔닝이 무작위 숫자를 정할 때, 항상 구간의 가운데 숫자를 고르도록 만듭니다. 사실 어떻게 하더라도 퀵셀렉트는 성공적으로 원하는 결과를 찾습니다.

이렇게 만든 랜더마이즈드 퀵셀렉트의 소요 시간을 측정해보면 다음과 같습니다.

quickselect elapsed time — 그림 6. 가장 작은 값을 찾는 퀵셀렉트의 소요 시간. 선은 회귀선.

여기서 입력 값의 크기 $n$ 을 두 배씩 키웠을 때, 소요 시간 또한 두 배씩 늘어남을 볼 수 있습니다. 따라서 이론적인 시간 복잡도의 기댓값 $\Theta(n)$ 을 따르는 근거가 됩니다.

랜더마이즈드 퀵소트

퀵소트는 각 데이터를 한 번씩 피벗으로 선택하며 소트합니다. 그리고 파티셔닝으로 나눈 두 구간에서 재귀적으로 반복합니다.

quicksort example — 그림 7. 퀵소트 예시. 퀵소트는 파티셔닝 이후 나뉜 부분에 대해 재귀적으로 퀵소트를 수행합니다. 각 데이터를 피벗으로 선택하므로 모든 데이터가 소트됩니다.

퀵소트의 수도코드는 다음처럼 간단히 만들 수 있습니다.

랜더마이즈드 퀵소트 ( $\textit{arr}$ , $\textit{begin}$ , $\textit{end}$ ) // 배열 $\textit{arr}\,$ 에서 구간 [ $\textit{begin}$ , $\textit{end}$ )을 소트

만약 $\textit{begin} = \textit{end}\,$ 이면 // 빈 구간이면

리턴

$i \leftarrow$ 랜더마이즈드 파티셔닝( $\textit{arr}$ , $\textit{begin}$ , $\textit{end}$ ) // $\textit{arr}$ [ $i$ ]가 소트됨

퀵소트( $\textit{arr}$ , $\textit{begin}$ , $\textit{i}$ )

퀵소트( $\textit{arr}$ , $\textit{i+1}$ , $\textit{end}$ )

시간 복잡도

퀵소트의 가장 이상적인 경우는 파티셔닝이 $n$ 개 중에 항상 중간값을 피벗으로 선택할 때입니다. 그러면 반쪽으로 나눠 재귀를 수행하므로, 머지 소트처럼 $\Theta(n \lg n)$ 의 시간이 들게 됩니다.

반면, 항상 최소값이나 최대값을 피벗으로 선택하면, 두 재귀는 각각 빈 구간과 하나가 줄어든 구간에서 재귀적으로 반복합니다. 다시 말해, $n$ 개의 데이터가 있으면, 재귀는 $n, n-1, \dots, 1$ 개에 대해 수행합니다. 이를 더하면 총 $\Theta(n^2)$ 의 시간이 걸립니다.

그러나 위 두 경우는 랜더마이즈드 퀵소트가 마주하는 여러 가능성 중 하나에 불과합니다. 따라서 시간 복잡도 $T_{rq}(n)$ 의 기댓값 $E[T_{rq}(n)]$ 을 계산해볼 필요가 있습니다.

퀵소트는 파티셔닝이 피벗 인덱스로 $i$ 를 선택하면, 두 재귀는 각각 $i$ 개와 $n-i-1$ 개에 대해 수행합니다. 그러므로 $T_{rq}(n)$ 은 파티셔닝과 두 재귀 수행에 걸리는 시간으로부터, 랜덤 변수로 구할 수 있습니다.

\begin{align*} T_{rq}(n) &= T_{rp}(n) + \sum_{i=0}^{n-1} I_i \left( T_{rq}(i) + T_{rq}(n-i-1) \right) \\ &= T_{rp}(n) + 2 \sum_{i=0}^{n-1} I_i T_{rq}(i) \end{align*}

빈 구간이면 두 줄만 수행하므로 $T_{rq}(0) = 2$ 이라고 하고, 이전처럼 인디케이터의 기댓값 $E[I_i]=1/n$ 을 이용합시다. 그러면 시간 복잡도 $T_{rs}$ 의 기댓값은 다음과 같습니다.

\tag{Eq.1} E[T_{rq}(n)] = T_{rp}(n) + \frac{2}{n} \left( \sum_{i=1}^{n-1} E[T_{rq}(i)] \right) + \frac{4}{n}

이제 다음과 같은 범위를 구해서, $E[T_{rq}(n)] = \Theta(n \lg n)$ 을 보일 것입니다.

c_1 n \lg n \leq E[T_{rq}(n)] \leq c_2 n \lg n

여기서 $c_1$ , $c_2$ 는 곧 정할 상수입니다.

첫 번째로, $E[T_{rq}(n)] \geq c_1 n \lg n$ 임을 귀납법으로 보이겠습니다. 이 식이 $m < n$ 인 $m$ 에 대해 성립한다고 하면, $\textrm{Eq.1}$ 으로부터 다음을 얻습니다. 여기서 $4/n$ 은 항상 $0$ 보다 크므로 버릴 수 있습니다.

E[T_{rq}(n)] \geq (4n + 7) + \frac{2}{n} c_1 \sum_{i=1}^{n-1} i \lg i

$\sum_{i=1}^{n-1} i \lg i$ 가 다음과 같다는 사실을 이용합시다.

\tag{Eq.2} \sum_{i=1}^{n-1} i \lg i \geq \frac{n}{2} \left( n \lg n - O(n) \right)

위 두 식을 연결하면 다음을 얻습니다.

\begin{align*} E[T_{rq}(n)] &\geq ( 4n + 7 ) + c_1 \left( n \lg n - O(n) \right) \\ &= c_1 n \lg n + \left( 4n - c_1 O(n) + 7 \right) \\ &\geq c_1 n \lg n \quad (\textrm{for some $c_1$}) \end{align*}

두 번째 식에서 $c_1$ 를 작게 선택하면 괄호 부분을 $0$ 보다 크게 만들 수 있습니다. 따라서 부등식에서 버릴 수 있게 되고, 증명이 끝납니다.

한편, $\textrm{Eq.2}$ 가 성립하는 이유는 간단히 알 수 있습니다. 먼저, 다음과 같이 합 $S_1$ , $S_2$ 를 정의합시다.

\begin{align*} S_1 &= 2\lg 2 + 3\lg 3 + \dots + (n-1)\lg (n-1) = \sum_{i=1}^{n-1} i \lg i \\ S_2 &= (n-2)\lg 2 + (n-3)\lg 3 + \dots + \lg (n-1) \end{align*}

그러면 $S_1 \geq S_2$ 이므로, 다음을 얻습니다.

\begin{align*} S_1 &= \frac{S_1 + S_2 \mathstrut}{2} \\ &= \frac{n}{2} \left( \lg 2 + \lg 3 + \dots + \lg (n-1) \right) \\ &= \frac{n}{2} \lg \left( (n-1)! \right) \\ &= \frac{n}{2} \left( n \lg n - O(n) \right) \end{align*}

마지막 단계는 스털링 근사Stirling’s approximation로부터 나옵니다.

두 번째로, $E[T_{rq}(n)] \leq c_2 n \lg n$ 도 비슷하게 보일 수 있습니다. 따라서 직접 해보는 것으로 남기고 생략하겠습니다. 다만 $\textrm{Eq.2}$ 에서 합 $\sum_{i}i \lg i$ 가 일정 수준 이상임을 이용했다면, 이 경우는 반대로 일정 수준 이하임을 이용할 수 있습니다.

자바로 구현하기

퀵소트는 이전 글에서처럼 스트레터지로 구현하겠습니다. 소팅 알고리즘의 인터페이스는 다음과 같이 만들었습니다.

public interface ArraySortStrategy<T> {
  public T[] sortArray(T[] arr, int begin, int end, Comparator<T> comp);
}

퀵소트 또한 이 인터페이스의 구현 클래스로 만들겠습니다. 먼저, 생성자에서 파티셔닝 알고리즘을 파라미터로 받습니다.

public class QuickStrategy<T> implements ArraySortStrategy<T> {
  private PartitionStrategy<T> strat;

  public QuickStrategy(PartitionStrategy<T> strat) {
    this.strat = strat;
  }

  // ...
}

그리고 배열을 소트하는 메소드는 다음과 같이 수도코드를 그대로 옮겨 만듭니다.

  public T[] sortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    if (begin >= end) {
      return arr;
    }

    int i = this.strat.partition(arr, begin, end, comp);
    this.sortArray(arr, begin, i, comp);
    this.sortArray(arr, i+1, end, comp);

    return arr;
  }
}

이는 다음 테스트 코드와 같이 사용할 수 있습니다. 여기서 파티셔닝은 항상 마지막 위치를 피벗으로 고르지만, 실제론 어떤 파티셔닝이든 상관없이 동작합니다.

  @Test
  public void testSort() {
    Integer[] unsorted = { 20, 30, 10, 40 };
    Integer[] expected = { 10, 20, 30, 40 };

    IntBinaryOperator chooseEnd = (begin, end) -> end-1;
    PartitionStrategy<Integer> partStrat = new RandTwoWayStrategy<>(chooseEnd);
    ArraySortStrategy<Integer> sortStrat = new QuickStrategy<>(partStrat);

    ArraySorter.sortArray(unsorted, sortStrat);

    assertArrayEquals(expected, unsorted);
  }

이렇게 만든 랜더마이즈드 퀵소트의 소요 시간을 재봅시다. 소트된 배열일 때와 반대로 소트되었을 때를 시나리오로 측정한 결과는 다음과 같습니다.

quicksort elapsed time — 그림 8. 퀵소트의 소요 시간. 각각 소트된 배열과 반대로 소트된 배열의 경우. 선은 회귀선.

그래프가 보여주듯이 이론적인 시간 복잡도의 기댓값 $\Theta(n \lg n)$ 을 따르는 근거가 됩니다.

세 부분으로 나누는 파티셔닝

파티셔닝 알고리즘을 이용하는 퀵소트는 피벗만 다음 재귀 구간에서 제외합니다. 따라서 입력 값에 피벗과 똑같은 값이 여러 개가 주어진다고 하더라도, 똑같은 값이 다음 구간에 포함됩니다. 그렇다면 피벗과 같은 값을 한번에 버릴 수 있다면 반복 횟수가 줄어들지 않을까요?

파티셔닝 알고리즘이 피벗과 똑같은 부분을 분리해서, 퀵소트가 그 부분을 다음 재귀에서 제외할 수 있게끔 만들어봅시다. 다시 말해, 피벗보다 작은 부분, 피벗과 같은 부분, 그리고 피벗 보다 큰 부분으로 나누는 것입니다.

이는 세 종류의 데이터를 소트하는 문제인 더치 내셔널 플래그Dutch national flag로 바라볼 수 있는데요. 다익스트라Dijkstra가 제시한 알고리즘을 참고하면, 세 부분으로 나누는 쓰리웨이three-way 파티셔닝은 이렇게 만들 수 있습니다.

아무렇게나 섞인 카드에서 왼쪽을 피벗으로 골랐다고 해봅시다. 먼저 비어있는 가상의 세 구간을 생각해봅시다. 구간 [ $b$ , $l$ )은 피벗보다 작은 것, [ $l$ , $m$ )은 피벗과 같은 것, 그리고 [ $u$ , $e$ )는 피벗보다 큰 것이 속할 것입니다.

파티셔닝은 $m$ 에 위치한 카드를 보면서, 이것을 세 구간 중 하나에 넣는 것으로 만들 것입니다.

만약 피벗과 같으면, 단순히 $m$ 에 하나를 더해서 구간 [ $l$ , $m$ )을 늘립니다. 이것이 그림의 첫 번째 줄에서 두 번째로 넘어가는 경우입니다.
피벗보다 작으면, 구간 [ $b$ , $l$ )에 넣어야 합니다. 이를 위해, $m$ 과 $l$ 위치의 카드를 바꾸고, $l$ 과 $m$ 을 하나씩 늘립니다. 그림의 두 번째 줄에서 세 번째로 넘어가는 경우입니다.
피벗보다 크면, 구간 [ $u$ , $e$ )에 넣어야 합니다. $m$ 과 $u$ 위치의 카드를 바꾸고, $u$ 를 하나 줄입니다. 그림의 세 번째 줄에서 네 번째로 넘어가는 경우입니다.

이를 수도코드로 표현하면 이렇게 됩니다.

파티셔닝 ( $\textit{arr}$ , $\textit{begin}$ , $\textit{end}$ ) // $\textit{arr}$ 의 구간 [ $\textit{begin}$ , $\textit{end}$ )을 세 부분으로 나눔

// 첫 번째 위치를 피벗으로 선택

$\textit{pivot} \leftarrow$ $\textit{arr}$ [ $\textit{begin}$ ]

// 구간 [ $\textit{begin}+1$ , $l$ )은 피벗보다 작은 것이 속함

$l \leftarrow \textit{begin}+1$

// 구간 [ $l$ , $m$ )은 피벗과 같은 것이 속함

$m \leftarrow l$

// 구간 [ $u$ , $end$ )는 피벗보다 큰 것이 속함

$u \leftarrow \textit{end}$

다음을 $m < u$ 인 동안 반복 // 구간 [ $m$ , $u$ )가 비어있지 않은 동안

// $m$ 위치의 값을 세 파티션 구간 중 한 곳으로 옮김

만약

\textit{arr}

[

m

]

< \textit{pivot}

이면

// 구간 [

\textit{begin}+1

l

)으로 옮김

$\textit{arr}$ [ $m$ ]과 $\textit{arr}$ [ $l$ ] 스왑

$l \leftarrow l + 1$

$m \leftarrow m + 1$

아니면 만약

\textit{arr}

[

m

]

> \textit{pivot}

이면

// 구간 [

u

\textit{end}

)으로 옮김

$u \leftarrow u - 1$

$\textit{arr}$ [ $m$ ]과 $\textit{arr}$ [ $u$ ] 스왑

아니면 // 피벗과 같은 값인 경우

// 구간 [

l

m

)으로 옮김

$m \leftarrow m + 1$

// 피벗을 구간 [ $l$ , $m$ )으로 옮김

$l \leftarrow l - 1$

$\textit{arr}$ [ $\textit{begin}$ ]과 $\textit{arr}$ [ $l$ ] 스왑

리턴 $l$ , $m$ // 피벗과 같은 구간

이를 바탕으로 파티셔닝부터 퀵소트까지 만들어봅시다.

먼저, 쓰리웨이 파티셔닝은 구간을 두 숫자로서 리턴합니다. 구간을 리턴하기 위해, 다음과 같이 두 숫자를 담는 클래스를 만듭시다.

public record IntPair(int first, int second) {}

그리고 피벗과 같은 구간을 리턴하는 파티셔닝의 인터페이스를 정의합니다.

public interface ThreePartitionStrategy<T> {
  public IntPair partition(T[] arr, int begin, int end, Comparator<T> comp);
}

수도코드를 그대로 옮겨 쓰리웨이 파티셔닝을 구현합시다.

public class ThreeWayStrategy<T> implements ThreePartitionStrategy<T> {
  public IntPair partition(T[] arr, int begin, int end, Comparator<T> comp) {
    assert begin >= 0;
    assert end > begin;
    assert arr.length >= end;

    T pivot = arr[begin];
    int l = begin+1;
    int m = l;
    int u = end;

    while (m < u) {
      if (isLessThan(arr[m], pivot, comp)) {
        swap(arr, l, m);
        l++;
        m++;
      } else if (isGreaterThan(arr[m], pivot, comp)) {
        u--;
        swap(arr, m, u);
      } else { // equal
        m++;
      }
    }

    l--;
    swap(arr, begin, l);

    return new IntPair(l, m);
  }
}

이를 랜더마이즈드 알고리즘으로 만들기 위해, 앞서 한 것과 같이 피벗을 무작위로 골라 첫 번째 위치와 바꿔서 구현합시다.

public class RandThreeWayStrategy<T> implements ThreePartitionStrategy<T> {
  IntBinaryOperator rand;

  public RandThreeWayStrategy(IntBinaryOperator rand) {
    this.rand = rand;
  }

  public IntPair partition(T[] arr, int begin, int end, Comparator<T> comp) {
    // select a random number
    int pivotIndex = this.rand.applyAsInt(begin, end);

    swap(arr, begin, pivotIndex);

    ThreePartitionStrategy<T> strat = new ThreeWayStrategy<>();
    return strat.partition(arr, begin, end, comp);
  }
}

이 파티셔닝을 이용한 퀵소트는, 기존의 퀵소트와 비슷하게 만들 수 있습니다.

public class ThreeWayQuickStrategy<T> implements ArraySortStrategy<T> {
  private ThreePartitionStrategy<T> strat;

  public ThreeWayQuickStrategy(ThreePartitionStrategy<T> strat) {
    this.strat = strat;
  }

  public T[] sortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    if (begin >= end) {
      return arr;
    }

    IntPair pivot = this.strat.partition(arr, begin, end, comp);
    this.sortArray(arr, begin, pivot.first(), comp);
    this.sortArray(arr, pivot.second(), end, comp);

    return arr;
  }
}

이렇게 만든 퀵소트는 다음 테스트 코드처럼 사용할 수 있습니다.

  @Test
  public void testSort() {
    Integer[] unsorted = { 2, 2, 1, 1, 3, 3 };
    Integer[] expected = { 1, 1, 2, 2, 3, 3 };

    IntBinaryOperator chooseEnd = (begin, end) -> end-1;
    ThreePartitionStrategy<Integer> partStrat = new RandThreeWayStrategy<>(chooseEnd);
    ArraySortStrategy<Integer> sortStrat = new ThreeWayQuickStrategy<>(partStrat);

    ArraySorter.sortArray(unsorted, sortStrat);

    assertArrayEquals(expected, unsorted);
  }

이렇게 만든 퀵소트의 소요 시간을 기존 퀵소트와 비교하면 다음과 같습니다. 여기서는 각각을 쓰리웨이 퀵소트와 투웨이 퀵소트라고 하겠습니다. 테스트 시나리오는 각각 배열에 같은 값만 있을 때와, 전부 다른 값이 반대로 소트된 때입니다.

three-way quicksort elapsed time — 그림 11. 쓰리웨이 퀵소트와 투웨이 퀵소트의 소요 시간. 선은 회귀선.

쓰리웨이 파티셔닝은 값이 모두 같은 배열이 주어지면 전부 피벗으로 선택하므로, 이를 이용하는 퀵소트는 다음 재귀로 실행할 데이터가 없어서 바로 끝나게 됩니다. 그리고 파티셔닝이 각 원소를 방문하므로, 이 경우 퀵소트는 $\Theta(n)$ 의 시간 복잡도를 가진다고 할 수 있습니다. 실제로 측정한 소요 시간은 이를 뒷받침하는 근거가 됩니다.

한편, 배열의 값이 전부 다를 경우 기존 퀵소트보다 다소 불리한 면을 보입니다. 사실 호어 파티션이 쓰리웨이 파티셔닝 알고리즘보다 스왑을 더 적게 수행합니다. 소트된 배열이 주어지는 경우를 생각해보면 알 수 있습니다. 스왑 횟수는 호어 파티션의 경우 한 번도 없지만, 쓰리웨이 파티셔닝은 배열의 크기에 비례합니다. 왜냐면 쓰리웨이 파티셔닝은 피벗과 다른 값이면 항상 스왑을 수행하기 때문입니다. 그러므로 이런 불필요한 스왑이 호어 파티션보다 불리한 소요 시간을 갖게 만든다고 볼 수 있습니다.

마치며

$k$ 번째 데이터를 찾는 순서 통계량 문제를 해결하는 퀵셀렉트와, 이에 필요한 파티셔닝 알고리즘을 이용해 퀵소트를 만들어보았습니다. 그리고 모든 알고리즘을 랜더마이즈드 알고리즘으로 디자인함으로써, 시간 복잡도가 입력 값에 따라 달라지지 않게 했습니다. 이 시간 복잡도를 분석하기 위해 확률론의 내용을 가져와서 기댓값을 계산하고, 소요 시간을 측정해 이를 뒷받침하는 결과를 얻었습니다. 마지막으로, 세 부분으로 나누는 파티셔닝을 통해, 배열에 같은 값이 많은 경우에 퀵소트를 개선해보았습니다.

본문의 자바 코드는 깃허브GitHub에서도 확인할 수 있습니다.

레퍼런스

Introduction to Algorithms (3rd ed., Thomas Cormen et al., 2009)
Algorithms (4th ed., Robert Sedgewick, 2011), 또는 알고리즘 (길벗, 2018)
Algorithm 63: Partition, Algorithm 64: Quicksort, Algorithm 65: Find (C. A. R. Hoare, 1961): 호어의 파티셔닝, 퀵소트, 그리고 퀵셀렉트 알고리즘.
Introduction to Probability with Statistical Applications (2nd ed., Géza Schay, 2016): 확률론.
Randomized Quick Sort and Selection (Illinois CS 473 Lecture Notes): 점화식을 이용한 퀵셀렉트 시간 복잡도 분석.
Java Microbenchmark Harness (JMH): 자바 코드의 소요 시간 측정에 사용한 도구.