무게추를 이용한 다음 퍼즐 문제는 유명해서 한번쯤 접했을 수도 있습니다.

이 문제는 소팅 알고리즘에서 중요합니다. 왜냐면 비교를 통해 데이터를 소트하는, 비교 기반comparison-based 소팅 알고리즘이 얼마나 빠를 수 있는지와 관련이 있기 때문입니다.

따라서 가장 간단한 경우로, 추가 세 개일 때를 보겠습니다. 그러면 저울을 최대 세 번 써야한다는 것을 알게 됩니다.

추의 무게가 각각 $w_1$, $w_2$, $w_3$이라고 하면, 저울을 사용하는 방법은 다음 두 가지 경우로 정리됩니다.

1. 운이 좋아서 두 번으로 끝난 경우: $w_1 < w_2$이고, $w_2 < w_3$인 걸 알아낸 경우.

2. 세 번이 필요한 경우: $w_1 < w_2$이고, $w_2 > w_3$이어서, 나머지 $w_1$와 $w_3$의 순서를 알아내야 할 때.

이런 과정을 말 대신 트리tree로 나타낼 수도 있습니다. 저울을 썼을 때 오른쪽이 내려오는지 여부를 기준으로 경우를 나눠봅시다. 그러면 각 노드node가 두 개의 자식 노드를 갖는 바이너리 트리binary tree로 나타낼 수 있게 됩니다.

각 노드는 저울의 사용을 나타내고, 마지막에 나타나는 노드, 즉 리프 노드leaf node는 결정된 추의 순서를 나타냅니다. 이런 트리를 결정 트리 혹은 디시전 트리decision tree라고 부릅니다. 그리고 노드의 높이가 곧 저울의 사용 횟수가 됩니다. 따라서 저울을 두 번이나 세 번 이용하게 된다는 사실 또한 알 수 있습니다.

한편, 추가 세 개인 경우는 디시전 트리를 그리기가 어렵지 않지만, 네 개부터 점점 쉽지 않아집니다. 왜냐면 $n$ 개의 추가 가질 수 있는 순서는 팩토리얼factorial, 즉 $n!=n {\cdots} 3 {\cdot} 2 {\cdot} 1$ 개로 빠르게 늘어나기 때문입니다. 추가 다섯 개면 $5!=5{\cdot}4{\cdot}3{\cdot}2{\cdot}1=120$ 개나 되는 리프 노드를 그려야 합니다.

하지만 디시전 트리의 높이는 적어도 얼마인지 알아낼 수 있습니다. 그리고 그 높이가 바로 저울의 사용 횟수를 의미하기 때문에, 이로부터 저울을 적어도 몇 번 써야하는지, 나아가 비교 기반 소팅 알고리즘의 시간 복잡도가 적어도 얼마인지 알게 됩니다.

바이너리 트리의 기본적인 성질은, 리프 노드가 $n$ 개이면 높이는 $\lg n$ 이상이라는 것입니다. 높이가 $n-1$이면 리프 노드는 기껏해야 $2^{n-1}$ 개이기 때문입니다.

디시전 트리는 리프 노드가 $n!$ 개인 바이너리 트리이므로 높이는 $\lg (n!)$ 이상이 됩니다. 그리고 스털링 근사Stirling’s approximation를 통해 $\lg (n!) \sim n \lg n = \Theta(n \lg n)$을 얻습니다. 그러므로 모든 비교 기반 소팅 알고리즘은 최악의 경우에 이 이상의 시간 복잡도, 즉 $\Omega(n \lg n)$을 갖게 됩니다. 다시 말해, $O(n)$의 시간이 걸리는 것은 이론적으로 존재할 수 없게 됩니다.

한편, 이론적으로 시간 복잡도의 한계를 구한 것과, 그런 시간 복잡도를 갖는 알고리즘을 생각해내는 것은 별개일 것입니다. 앞으로의 내용을 통해, 최악의 경우에 $\Theta(n \lg n)$의 시간이 드는 머지 소트merge sort를 만들어볼 것입니다. 방금 살펴본 사실에 비추어본다면, 이 알고리즘은 최악의 경우에 최적의 시간 복잡도를 가졌다고 말할 수 있습니다. 그리고 이전 글과 이어지는 내용으로서, 인서션 소트insertion sort를 이용해 머지 소트를 개선해보고, 머지 소트를 이용해 인버전inversion을 세는 알고리즘도 만들어보겠습니다. 이를 통해 머지 소트의 최적화 방법과, 머지 소트와 인버전 간의 관계를 알 수 있습니다.

작은 문제로 나눠서 해결하기

섞여있는 카드를 소트해야 한다고 예를 들어보겠습니다. 머지 소트의 기본적인 생각은 소트된 두 카드 덱을 하나의 덱으로 합치며 소트하는 것입니다. (그래서 합치는merge 소트입니다.)

먼저, 각 덱에서는 맨 앞의 카드가 가장 낮다는 사실을 이용합니다. 그런데 맨 앞의 카드 중 더 낮은 것이 전체 중에서 가장 낮은 것으므로 그것을 가져옵니다. 그리고 이 과정을 반복하면, 자연스럽게 하나의 덱으로 소트됩니다. 이 과정을 머지merge한다고 부릅니다.

그런데 이렇게 머지 하기 전에는, 작은 크기의 덱이 미리 소트되어 있어야 합니다. 여기서 카드가 하나 뿐인 덱은 이미 소트되었다고 볼 수 있습니다. 따라서 머지 소트가 해야할 일은, 먼저 모든 카드를 하나씩 덱으로 나눈 다음, 이로부터 머지를 반복하는 것입니다.

이것을 수도코드로 표현하면 다음과 같습니다.

구간을 표현하는 두 인덱스는 반열린구간 $[\textit{begin}, \textit{end})$을 나타냅니다.

수도코드가 보여주듯이, 머지 소트는 데이터를 바로 소트하는 것이 아니라, 일단 반씩 나누어 다음 재귀에 맡깁니다. 그러다가 배열의 크기가 하나가 되어서야 본격적인 소트를 시작합니다. 그러면 머지를 통해 소트된 부분이 점점 커지면서 소트가 끝납니다.

마지막 단계에서 쓰는 머지는 카드 예시에서 봤던 두 덱을 합치는 과정입니다. 머지할 두 구간이 $[\textit{begin}, \textit{mid})$, $[\textit{mid}, \textit{end})$로 주어진다고 하면 수도코드는 다음과 같습니다.

반복문에서는 더 먼저와야할 데이터를 가져옵니다. 여기서 두 데이터의 순서가 같은 경우를 잘 처리하면, 소팅 알고리즘이 기존 데이터가 갖고있던 순서를 유지하도록, 즉 스테이블stable하도록 만들 수 있습니다.

여기선 머지 소트를 스테이블하게 만들기 위해, 순서가 같으면 인덱스가 작은 쪽, 즉 $\textit{lower}\,$ 구간의 데이터를 가져옵니다. 그러면 같은 순서의 데이터는 인덱스가 낮은 것이 항상 낮은 채로 유지되므로, 소팅이 스테이블하게 됩니다. (반대로 인덱스가 높은 쪽에서 먼저 가져오면 스테이블하지 않게 됩니다. 확인해보세요.)

시간 복잡도 분석

머지는 구간의 길이가 $n$이면 반복문을 $n$ 번 수행합니다. 반복문은 네 줄의 수도코드를 수행하고, 반복문 외에는 다섯 줄을 수행하므로, 머지의 시간 복잡도 $T_m(n)$은 $4n + 5$로 쓸 수 있습니다.

그렇다면 머지 소트의 시간 복잡도 $T(n)$을 구해봅시다. 머지 소트는 어떤 입력값이든 똑같은 다음 점화식recurrence relation을 가집니다.

여기서 쓰인 천장 함수 혹은 실링 함수ceiling function $\lceil x \rceil$는, $\lceil 3.1 \rceil = 4$처럼 소수점이 있다면 올리기 위해 쓰였습니다. 구간을 반으로 나눈 재귀 수행 때문에, 점화식은 $T(\lceil n / 2 \rceil)$과 $T(\lfloor n / 2 \rfloor)$을 가집니다. 그리고 머지 때문에 $T_m(n)$가 포함됩니다. 그렇지 않고 $n \leq 1$이라면, 배열을 바로 리턴하는 부분 때문에 $T(n)=2$가 됩니다.

플로어 함수와 실링 함수가 실제로 역할을 하는 경우는, 구간의 크기 $n$이 $5$ 처럼 홀수라서 $n/2$에 소수점이 나타날 때입니다. 즉 $\lfloor 2.5 \rfloor = 2$, $\lceil 2.5 \rceil = 3$ 처럼 각각 소수점 버림과 올림을 맡습니다. 하지만 $\lceil n/2 \rceil$와 $\lfloor n/2 \rfloor$는 점화식을 풀어서 얻는 $T(n)$에 결과적으로 영향을 미치지 않습니다. 그 이유는 긴 증명보다, $\lceil x \rceil$는 $x$와 차이가 $1$ 미만이므로 무시할만큼 작기 때문이라고 대신 설명하겠습니다. 따라서 단순히 $n/2$으로 바꾸더라도 무방합니다.

$n$이 $2, 4, 8, \dotsc$ 같은 $2^k$ 꼴이라고 가정하고 이 식을 전개하면 $T(n) = \Theta(n \lg n)$을 얻습니다.

여기서 $T(n/2)$을 $T(1)$까지 줄이기 위해 $\lg (n-1)$ 번 반복 적용이 필요하다는 점과, $2^kT_m(n/k)$ 꼴은 $\sim\!4n$이라는 점을 이용합니다.

자바로 구현하기

이전 글에서 소팅 알고리즘을 스트레터지 패턴strategy pattern으로 구현하기 위해 다음 인터페이스를 만들었습니다.

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

여기서도 머지 소트를 스트레터지로 구현하겠습니다. 앞으로 여러 방법으로 머지 소트를 만들 것이기 때문에, 먼저 추상 머지 클래스를 만듭시다.

public abstract class AbstractMergeStrategy<T>
    implements ArraySortStrategy<T> {
  // ...
}

이어서 sortArray() 메소드를 만듭시다. aux 배열은 머지 결과를 임시로 갖기 위해 만든 것이고, 실제 소트는 다른 메소드에 맡깁니다. 소팅 알고리즘을 본격적으로 구현할 메소드는 서브 클래스에서 제공할 것입니다.

  private T[] aux;

  public T[] sortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    this.aux = arr.clone();

    this.mergeSortArray(arr, begin, end, comp);

    this.aux = null;

    return arr;
  }

  abstract protected void mergeSortArray(T[] arr, int begin, int end, Comparator<T> comp);

그리고 각각의 머지 소트 구현에서 공통으로 쓸 머지는 다음과 같이 수도코드를 그대로 옮겨서 만듭니다.

  protected void mergeArrays(T[] arr, int begin, int mid, int end, Comparator<T> comp) {
    // lower <- [lowerBegin, lowerEnd)
    int lowerBegin = begin;
    int lowerEnd = mid;
    // upper <- [upperBegin, upperEnd)
    int upperBegin = mid;
    int upperEnd = end;

    for (int i = begin; i < end; ++i) {
      lessOrEqual = isLessOrEqualLowerBegin(arr, lowerBegin, lowerEnd, upperBegin, upperEnd, comp);
      if (lessOrEqual) {
        this.aux[i] = arr[lowerBegin++];
      } else {
        this.aux[i] = arr[upperBegin++];
      }
    }

    System.arraycopy(this.aux, begin, arr, begin, end-begin);
  }

여기서 lessOrEqual은, lower의 첫 데이터가 upper의 첫 데이터보다 낮은지의 여부로, 수도코드 상에선 한 줄로 구했던 것입니다. 그런데 실제 구현은 한 쪽 구간이 비었을 가능성도 고려해야 합니다. 그런 경우, 다른 쪽이 더 작다고 알려줍니다.

  public static <T> boolean isLessOrEqualLowerBegin(T[] arr, int lowerBegin, int lowerEnd, int upperBegin, int upperEnd,
      Comparator<T> comp) {
    assert lowerEnd >= lowerBegin;
    assert upperBegin >= lowerEnd;
    assert upperEnd >= upperBegin;
    assert upperEnd > lowerBegin;

    if (lowerBegin == lowerEnd) {
      return false;
    }
    if (upperBegin == upperEnd) {
      return true;
    }

    return isLessThanOrEqualTo(arr[lowerBegin], arr[upperBegin], comp);
  }

한편, 마지막에 두 데이터를 비교하는 메소드는, 이전 글처럼 유틸 메소드로 분리한 것입니다.

public class Comparators {
  // ...

  public static <T> boolean isLessThanOrEqualTo(T source, T target, Comparator<T> comparator) {
    return comparator.compare(source, target) <= 0;
  }
}

마지막으로, 머지 소트는 서브 클래스에서 수도코드를 그대로 옮겨 구현합니다.

public class TopDownMergeStrategy<T> extends AbstractMergeStrategy<T> {
  @Override
  protected void mergeSortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    if (end - begin <= 1) {
      return;
    }

    int mid = begin + (end - begin) / 2;

    this.mergeSortArray(arr, begin, mid, comp);
    this.mergeSortArray(arr, mid, end, comp);
    this.mergeArrays(arr, begin, mid, end, comp);
  }
}

이렇게 만든 머지 소트는 다음 테스트 코드처럼 사용할 수 있습니다. 이전 글에서 만들어둔 별도의 ArraySorter 클래스를 통해 데이터를 소트합니다. 이 메소드에 배열과 스트레터지를 넘기면, 전체 구간을 오름차순으로 소트합니다.

  @Test
  public void testSort() {
    Integer[] toSort = { 20, 30, 10, 40 };
    Integer[] expected = { 10, 20, 30, 40 };
    ArraySortStrategy<Integer> strat = new TopDownMergeStrategy<>();

    ArraySorter.sortArray(toSort, strat);

    assertArrayEquals(expected, toSort);
  }

이 케이스는 실제로 잘 통과합니다.

소요 시간 측정

앞서 분석했던대로, 어떤 입력값이든 $\Theta(n \lg n)$의 시간 복잡도를 가진다는 사실을 확인할 차례입니다. 다음은 이미 소트된 배열과 반대 순서로 소트된 배열을 각각 입력값으로 했을 때 측정한 소요 시간입니다.

이 결과가 보여주듯이, 두 입력값이 경우 대체로 이론적인 시간 복잡도 $\Theta(n \lg n)$을 따른다고 볼 수 있습니다.

크기가 작은 경우 개선하기

시간 복잡도를 분석해 얻은 $\Theta(n \lg n)$ 같은 결과는 $n$이 커짐에 따른 경향성을 보여주지만, 반대로 $n$이 작을 때는 얘기해주는 것이 없습니다. 예를 들어, 인서션 소트는 최악의 경우에 $\Theta(n^2)$의 시간이 걸리므로 머지 소트보다 느리겠지만, $n$이 작을 때는 그렇게 말할 수 없습니다.

그러면 $n$이 작을 때 인서션 소트와 머지 소트의 소요 시간을 직접 측정해봅시다. 다음은 소트된 배열과 그 반대 순서로 된 배열일 때를 각각 시나리오로 한 결과입니다.

배열이 이미 소트된 경우, 인서션 소트의 소요 시간이 더 적고, 반대로 소트된 경우, $n = 2^4$ 부근까지 그렇습니다.

그러면 머지 소트에 작은 배열이 주어졌을 경우, 인서션 소트로 대신하면 소요 시간이 줄어들지 않을까요? 구현을 통해 살펴보겠습니다.

인서션 소트 섞기

만약 배열의 크기 $n$이 어떤 크기 $k$ 이하라면 인서션 소트를 대신 한다고 해봅시다. 그렇다면 $\textrm{Eq.1}$에서 구했던 머지 소트의 시간 복잡도는 최악의 경우에 이렇게 바뀝니다.

여기서 $T_i(n)$은 인서션 소트의 시간 복잡도이고, 이전 글에서 분석했던 것처럼, 어떤 상수 $c$에 대해 $T_i(n) \sim cn^2 = \Theta(n^2)$ 입니다.

계산의 편의를 위해, 이번에도 $n = 2^s$ 꼴이고, $k = 2^t$ 꼴이라고 하겠습니다. 앞에서 했던 대로 전개하면 다음을 얻습니다.

여기서 $k = 1$이면 인서션 소트 없이 머지 소트만 하는 경우이고, $T(n)$은 $\Theta(n \lg n)$가 됩니다. 반면, $k$가 $n$에 가까워지면 $\Theta(n^2)$이 됩니다. 처음부터 인서션 소트를 하는 것과 같기 때문입니다. 이것은 머지 소트보다 더 큰 시간 복잡도입니다.

정리하면 $k$ 값은 낮은 숫자 중에 고르는 것이 유리합니다.

자바로 구현하기

앞서 $k$ 값을 정할 필요가 있었는데, 여기서는 $k=7$로 하겠습니다. 즉 크기가 이 이하인 배열은 인서션 소트로 대신합니다. 여기에 이론적인 의미가 있다기보다는, 개선이 실제로 나타나기 때문에 선택한 값입니다. 이와 비슷하게, 자바의 구현인 OpenJDK에서는 일곱 개 미만일 때 전환합니다.

인서션 소트는 이전 글에서 만들었던 InsertionStrategy 클래스를 그대로 이용합니다.

public class TopDownInsMergeStrategy<T> extends AbstractMergeStrategy<T> {
  private static int THRESHOLD = 7;

  @Override
  protected void mergeSortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    if (end - begin <= 1) {
      return;
    }

    // do insertion sort if small
    if (end - begin <= THRESHOLD) {
      ArraySorter.sortArray(arr, begin, end,
        new InsertionStrategy<>(), comp);
      return;
    }

    int mid = begin + (end - begin) / 2;

    this.mergeSortArray(arr, begin, mid, comp);
    this.mergeSortArray(arr, mid, end, comp);
    this.mergeArrays(arr, begin, mid, end, comp);
  }
}

이렇게 구현한 소트는 기존 머지 소트와 똑같은 테스트 케이스를 통과합니다. 또한 여전히 스테이블합니다. 인서션 소트와 머지 소트가 둘 다 스테이블하기 때문입니다.

소요 시간 측정

위와 같이 구현한 소트를 기존 머지 소트와 비교해봅시다.

인서션 소트를 섞었을 때, 최악의 경우에는 대략 10–20 퍼센트 줄어든 소요 시간을, 최선의 경우에는 20–40 퍼센트를 보여줍니다. 한편, 이렇게 줄어든 소요 시간의 폭은 $n$이 늘어날 수록 줄어드는 경향을 보입니다.

아래에서 위로 반복하기

이전 글에서, 재귀 알고리즘은 반복 알고리즘으로 바꿀 수 있다고 했습니다. 재귀를 통해 배열을 작게 나누는 머지 소트 또한 예외는 아닙니다. 재귀로 구간을 하나씩 나누는 과정 없이, 처음부터 구간의 크기를 하나로 시작해 머지를 시작하면 반복문으로도 충분하게 됩니다.

여기서는 구간의 크기를 $\textit{size}_\textit{\small m}$이라고 합시다. 이 크기로 배열을 나눈 뒤, 두 개씩 머지할 구간으로 선택합니다. 이것을 $[\textit{begin}_\textit{\small m}, \textit{mid}_\textit{\small m})$과 $[\textit{mid}_\textit{\small m}, \textit{end}_\textit{\small m})$으로 나타냅시다.

기존 머지 소트는 구간을 반으로 나누면서 재귀를 수행하므로 탑 다운top-down 방식이라고도 부릅니다. 반면 반복문을 이용한 것은 크기를 늘려가므로 바텀 업bottom-up으로 부릅니다. 바텀 업 머지 소트는 수도코드로 다음과 같이 옮길 수 있습니다.

이렇게 바꾸더라도 시간 복잡도는 그대로 $\Theta(n \lg n)$이 됩니다. 바깥쪽 반복문이 대략 $\lg n$ 번 반복하고, 안쪽 반복문이 배열의 $n$ 개의 데이터에 모두 접근하기 때문입니다. 하지만 바텀 업 방식은 재귀 스택을 쓰지 않으므로 그만큼 메모리를 덜 쓴다는 장점이 있습니다.

자바로 구현하기

자바 코드로는 탑 다운 방식의 스트레터지를 만들어 수도코드를 그대로 옮겨 만듭니다.

public class BottomUpMergeStrategy<T> extends AbstractMergeStrategy<T> {
  @Override
  protected void mergeSortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    int size = end - begin;

    for (int mergeSize = 1; mergeSize < size; mergeSize *= 2) {
      for (int mergeBegin = begin; mergeBegin < end; mergeBegin += 2*mergeSize) {
        int mergeMid = mergeBegin + mergeSize;
        if (mergeMid >= end) {
          break;
        }

        int mergeEnd = Math.min(mergeMid + mergeSize, end);

        this.mergeArrays(arr, mergeBegin, mergeMid, mergeEnd, comp);
      }
    }
  }
}

이 또한 아까와 같은 똑같은 테스트 케이스를 통과합니다.

인버전 개수 세기

인버전이란 반대 순서로 있는 두 데이터를 말합니다. 그렇다면 인버전의 개수를 세는 알고리즘은 어떻게 만들 수 있을까요? 인서션 소트는 스왑 횟수가 곧 인버전 개수입니다. 따라서 이를 통해 세는 알고리즘은 인서션 소트처럼 최악의 경우 $\Theta(n^2)$의 시간 복잡도를 가집니다.

하지만 머지 소트에서도 인버전을 셀 수 있습니다. 머지 과정을 보면 인덱스가 큰 쪽에서 다음 데이터를 가져올 때, 작은 쪽에 있는 모든 데이터와 인버전을 이룹니다. 반면 작은 쪽에서 가져올 경우, 이것과 이루는 인버전은 없습니다.

따라서 인덱스가 큰 쪽에서 데이터를 가져올 때마다, 작은 쪽 구간의 크기를 더해나가면 인버전의 총 개수가 됩니다. 예를 들어, 다음과 같이 머지 과정에서 numInv 변수로 인버전을 세도록 바꿔볼 수 있습니다.

  protected int mergeArrays(T[] arr, int begin, int mid, int end Comparator<T> comp) {
    int numInv = 0; 

    // ...

    for (int i = begin; i < end; ++i) {
      if (isLessOrEqualLowerBegin(arr, lowerBegin, lowerEnd, upperBegin, upperEnd, comp)) {
        aux[i] = arr[lowerBegin++];
      } else {
        aux[i] = arr[upperBegin++];
        numInv += lowerEnd - lowerBegin; 
      }
    }

    return numInv; 
  }

그리고 이렇게 가져온 개수를 전부 더하도록 머지 소트를 수정하면 총 인버전 개수를 셀 수 있게 됩니다. 완성은 직접 해보는 것으로 남기겠습니다.

마치며

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

레퍼런스

• Introduction to Algorithms (3rd ed., Thomas Cormen et al., 2009)

• Algorithms (4th ed., Robert Sedgewick, 2011), 또는 알고리즘 (길벗, 2018)

• Design Patterns: Elements of Reusable Object-Oriented Software (Erich Gamma et al., 1995), 또는 GoF의 디자인 패턴: 재사용성을 지닌 객체지향 소프트웨어의 핵심요소 (프로텍미디어, 2015): 스트레터지 패턴 소개.

• The Art of Computer Programming, Vol. 3 (2nd ed., Donald Knuth, 1998), 또는 The Art of Computer Programming 3 (한빛미디어, 2008): 저울의 최소 비교 횟수 문제.