버블 소트는 좋은 방법이 아닌 것 같습니다.

I think the bubble sort would be the wrong way to go.

— 버락 오바마Barack Obama (2007)

뒤집혀있는 카드 중에 원하는 카드를 어떻게 빨리 찾을 수 있을까요?

만약 아무런 정보가 없다면, 가장 단순한 방법으로 하나하나 뒤집어보는 수밖에 없습니다. 이런 방법은 시퀀셜 서치sequential search, 또는 리니어 서치linear search라고 부릅니다. 최악의 경우에 시간 복잡도는 모든 데이터 $n$ 개를 확인해봐야 하므로 $\Theta(n)$ 이 됩니다.

그림 1. 원하는 카드가 나올 때까지 앞에서부터 뒤집어보는 시퀀셜 서치.

하지만 카드에 대한 정보가 있다면 서치에 활용할 수 있습니다. 특히 여기서 주목할 것은 다음과 같은 것들입니다.

카드 간에 정해놓은 순서가 있는가
카드가 그 순서대로 있는가

여기서, 정해놓은 순서를 오더링ordering이라고 부릅니다. 그리고 그 순서에 따라 차례로 두는 것을 정렬 혹은 소트sort한다고 말하고, 그런 알고리즘을 소팅 알고리즘sorting algorithm이라고 부릅니다.

앞으로의 내용을 통해, 이 두 가지 정보로 비롯된 알고리즘으로서 서치 알고리즘과 소팅 알고리즘을 만나볼 것입니다. 이 둘은 서로 밀접한 관련이 있기도 하지만, 그 자체로 광범위하게 활용할 수 있기 때문에 중요한 주제이기도 합니다.

예를 들어, 뒤집힌 카드가 소트되어 있다는 걸 안다면, 원하는 카드를 훨씬 빠르게 찾도록 만들 수 있습니다. 바이너리 서치binary search가 바로 그 정보를 활용해서, 최악의 경우에도 $\Theta(\lg n)$ 의 시간 복잡도를 가집니다. 한편, 소트되어 있는지 모르더라도, 한번 소트하고 나면 그 다음에는 시퀀셜 서치를 할 필요가 없어집니다. 따라서 빠른 소팅 알고리즘 또한 필요하게 됩니다.

여기서는 서치 알고리즘으로 바이너리 서치를 구현해보며 동작 원리를 이해해볼 것입니다. 소팅에는 다양한 알고리즘이 있지만, 여기서는 간단한 것으로 삽입 정렬 혹은 인서션 소트insertion sort라는 것을 보겠습니다. 재밌는 것은 이 알고리즘이 어떤 경우에 느린지 분석해보면, 어떤 데이터를 더 소트된 것으로 볼 수 있는지 한 가지 기준이 마련된다는 것입니다. 나중에 보겠지만, 데이터에 인버전inversion이라고 하는 것이 적을 수록 데이터는 더 소트됐다고 할 것입니다. 따라서 인서션 소트가 한꺼번에 더 많은 인버전을 없애도록 성능 개선을 시도해볼 수도 있습니다. 이것이 마지막으로 만나볼 알고리즘인 셸 소트Shell sort입니다.

순서를 이용한 서치

카드가 순서대로 있다는 걸 안다면, 어떻게 원하는 카드를 가장 빨리 찾을 수 있을까요?

물론 아무거나 찍어서 한번에 찾을 수도 있겠지만, 그렇게 하면 최악의 경우엔 모든 카드를 확인해봐야 하므로 시퀀셜 서치의 시간 복잡도 $\Theta(n)$ 과 다를 게 없습니다. 운이 좋은 경우는 항상 한번에 찾을 수 있기 때문에, 여기서 관심을 갖는 것은 최악의 경우에 드는 시간을 줄이는 것입니다.

그렇다면 답은 항상 가운데부터 확인하는 것입니다. 예를 들어, 뒤집힌 카드 중에 숫자 8을 찾는다고 해봅시다. 그 중 가운데 카드가 6이라면, 그 전의 카드는 숫자 8보다 작은 것이 분명해지므로 볼 필요가 사라집니다. 이런 식으로 남은 절반에서 이 과정을 반복합니다.

그림 2. 바이너리 서치로 숫자 8을 찾는 예시. 가운데에서 원하는 숫자를 찾을 때까지 카드를 반으로 줄입니다.

이 과정을 어떻게 수도코드로 표현할 수 있을까요?

먼저, 서치 구간의 시작은 $\textit{begin}\,$ , 마지막은 $\textit{end}\,$ 로 표현하겠습니다. 다만 $\textit{end}\,$ 는 마지막 데이터의 다음을 가리킵니다. 이처럼 마지막이 제외된 구간을 반열린구간half-open interval이라고 부르고 $[\textit{begin}, \textit{end})$ 로도 표현합니다. 이렇게 하면, 구간이 비었다는 사실은 $\textit{begin} = \textit{end}\,$ 로 나타낼 수 있습니다.

배열 상에서 서치를 한다면 이런 수도코드로 정리해볼 수 있습니다.

바이너리 서치 ( $\textit{arr}$ , $\textit{target}$ ) // 배열 $\textit{arr}\,$ 에서 $\textit{target}\,$ 을 찾으면 인덱스를, 아니면 $-1$ 을 리턴

\textit{target}\,

을 찾을 구간을 반열린구간 [

\textit{begin}

\textit{end}

)로 표현

$\textit{begin} \leftarrow 0$

$\textit{end} \leftarrow \textit{arr}\,$ 의 크기

다음을 $\textit{begin} < \textit{end}$ 인 동안 반복 // 구간 [ $\textit{begin}, \textit{end}$ )가 비어있지 않는 동안

// 가운데 데이터 선택

$\textit{mid} \leftarrow \lfloor (\textit{begin} + \textit{end}) / 2 \rfloor$

$\textit{midValue} \leftarrow \textit{arr}[\textit{mid}]$

// 찾은 경우 리턴

만약

\textit{midValue} = \textit{target}

이면

리턴

\textit{mid}

// 못 찾았다면, 필요없는 절반을 제외

만약

\textit{midValue} < \textit{target}

이면

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

아니면

$\textit{end} \leftarrow \textit{mid}$

리턴 $-1$ // 찾기 실패

여기서 $\lfloor x\rfloor$ 는 플로어 함수floor function 혹은 바닥 함수라고 부르는 것인데, 소수점을 버리기 위해 사용했습니다. 예를 들어 $\lfloor 3.9 \rfloor = 3$ 이고 $\lfloor 3 \rfloor = 3$ 입니다.

한편, 자료에 따라서는 양쪽을 구간에 포함시킨, 소위 닫힌구간closed interval $[\textit{begin}, \textit{end}]$ 를 고르기도 합니다. 그러면 구간이 비어있지 않다는 표현은 $\textit{begin} \leq \textit{end}\,$ 로 달라지고, $\textit{end}\,$ 의 초기화와 반복문의 조건도 바뀌어야 합니다. 어느쪽이든 편한 표현 방식을 선택하면 됩니다.

알고리즘이 올바른지 확인하기

벨 연구소와 IBM에서 존 벤틀리Jon Bentley가 조사한 바에 따르면, 프로그래머 열 명 중 한 명 정도만 바이너리 서치를 올바르게 만들었다는 기록이 있습니다. 이런 점에 비추어볼 때 구현하기가 비교적 까다로운 알고리즘인 것입니다.

그러면 수도코드가 올바르게 동작하는지 어떻게 확신할 수 있을까요? 바이너리 서치가 동작하는 이유를 이렇게 정리해봅시다.

서치 대상 $\textit{target}\,$ 이 배열 $\textit{arr}\,$ 에 있다면, 알고리즘 실행 내내 $\textit{target}\,$ 의 인덱스 $i$ 는 $[\textit{begin}, \textit{end})$ 안에 있다. 즉, $\textit{begin} \leq i < \textit{end}$ 이다.
반대로, 배열에 없다면 그 인덱스 $i$ 는 $[\textit{begin}, \textit{end})$ 안에 없다.

이 중에 첫 번째 문장이 항상 성립함을 보이겠습니다. 이를 위해 반복문의 시작 직전, 반복, 그리고 종료 직후로 경우를 나눠 따져보겠습니다. 이 문장은 반복문 동안 변하지 않는 사실이기 때문에, 루프 인베리언트loop invariant라고도 부릅니다.

첫 번째로, 시작 직전을 봅시다. 이때 수도코드는 $\textit{begin}\,$ 과 $\textit{end}\,$ 를 초기화합니다.

$\textit{begin} \leftarrow 0$

$\textit{end} \leftarrow \textit{arr}\,$ 의 크기

처음에 서치 대상이 배열에 있다고 가정한 것은, 그 인덱스 $i$ 가 $\textit{begin} \leq i < \textit{end}\,$ 라는 것입니다. 따라서 루프 인베리언트가 성립합니다. (너무 당연해보이지만 소개 차원에서 해봤습니다.)

두 번째로, 반복 과정을 봅시다. 반복문이 실행됐으므로 구간은 비어있지 않은 것, 즉 $\textit{begin} < \textit{end}\,$ 입니다. 만약 가운데 데이터가 서치 대상보다 작다면, $i$ 는 큰 쪽 절반 구간 $[\textit{mid}+1, \textit{end})$ 에 있는 것입니다. 이 때 다음 수도코드가 실행되고, 서치 구간이 정확히 $[\textit{mid}+1, \textit{end})$ 로 줄어듭니다.

만약

\textit{midValue} < \textit{target}

이면

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

따라서 다음 반복의 시작까지 루프 인베리언트가 성립하게 됩니다. 반대로, $i$ 가 다른 쪽에 속할 때도 마찬가지입니다. (직접 해보세요.)

마지막으로, 반복이 끝난 직후를 봅시다. 만약 서치 대상을 찾았다면, 실제로 그 인덱스가 $[\textit{begin}, \textit{end})$ 에 있었던 것입니다. 따라서 끝난 직후에도 성립합니다.

결론적으로 루프 인베리언트를 통해, 반복 조건과 반복마다 줄이는 구간은 올바르다는 걸 확인했습니다. 반대로 이 두 가지가 살짝이라도 달라졌을 때, 루프 인베리언트는 성립하지 않게 되고 알고리즘은 동작하지 않습니다. (확인해보세요.)

정수 오버플로우 버그

방금 수도코드가 올바르게 동작한다는 것을 확인했습니다. 그런데 수도코드 상에서는 보이지 않지만 구현 시 만나게 되는 버그가 있습니다.

$\textit{mid} \leftarrow \lfloor (\textit{begin} + \textit{end}) / 2 \rfloor$

가운데 인덱스를 구할 때, 숫자가 큰 경우 덧셈에서 정수 오버플로우integer overflow를 일으킬 수 있기 때문입니다. 이 글에 따르면 자바Java 라이브러리의 바이너리 서치에도 9년 가까이 있었던 버그이기도 합니다.

$\textit{mid} \leftarrow \textit{begin} + \lfloor (\textit{end} - \textit{begin}) / 2 \rfloor$

이 문제를 고치는 방법은 오버플로우가 일어나지 않도록 이렇게 뺄셈으로 대신 표현하는 것입니다.

시간 복잡도 분석

최선의 경우는, 서치 대상이 운 좋게 가운데에 있어서 바이너리 서치가 한 번의 확인으로 끝날 때입니다. 따라서 크기와 상관 없이 끝나므로 시간 복잡도는 $\Theta(1)$ 가 됩니다.

최악의 경우는, 서치 대상이 배열에 없어서 서치 구간이 빌 때까지 계속 반복할 때입니다. 반복문은 여섯 줄의 코드를 수행한 후 구간을 반으로 줄이므로, 반복문의 시간 복잡도 $T(n)$ 은 다음 점화식recurrence relation을 가집니다.

T(n) = 6 + T\left(\frac{n}{2}\right)

전개하면 $\Theta(\lg n)$ 을 얻습니다.

\begin{align*} T(n) &= 6 + 6 + T\left(\frac{n}{4}\right) \\ &= \underbrace{6 + 6 + \dots + 6}_{\small 6\lg n} + T(1) \\ &= \Theta(\lg n) \end{align*}

그런데 이것은 부분적인 해답으로서, $n$ 이 $1, 2, 4, 8, \dots$ 인 경우를 구한 것입니다. 그래서 $T(n/2)$ 항이 $T(1)$ 로 이어진 것입니다.

일반적인 $n$ 의 경우, 구간이 $\lfloor n/2 \rfloor$ 만큼 줄어듭니다. 따라서 점화식은 이렇습니다.

T(n) = 6 + T\left(\Big\lfloor\frac{n}{2}\Big\rfloor\right)

그러면 아까처럼 전개했을 때 $6$ 이 몇 개인지 문제가 됩니다.

\begin{align*} T(n) &= 6 + 6 + T\left(\bigg\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\bigg\rfloor\right) \\ &= \underbrace{6 + 6 + \dotsb + 6}_{\small\textrm{?}} + T(1) \end{align*}

그 개수는 다음과 같이 트리를 그려보면, $\lfloor\lg n \rfloor$ 임을 알 수 있습니다. 구간의 길이를 이진수로 나타냈을 때, 구간이 줄어들 때마다 크기가 오른쪽 시프트right shift 연산을 한 것처럼 나타납니다.

number of iterations — 그림 3. 구간이 줄어드는 횟수를 구하는 트리. 트리의 각 노드 값은 구간의 길이 $n$ 을 나타냅니다. 왼쪽 트리는 한 수준 위로 올라갈 때마다 $n$ 에서 $\lfloor n/2 \rfloor$ 을 계산합니다. 오른쪽 트리는 왼쪽 트리를 이진수로 옮긴 것이고, 위로 올라가는 것은 오른쪽 시프트 연산에 대응됩니다. 맨 오른쪽에 적힌 $\lfloor \lg n \rfloor$ 은 구간의 길이 $n$ 을 $1$ 로 줄이기 위해 필요한 반복 횟수가 됩니다.

따라서 구간은 $\lfloor\lg n\rfloor$ 번 줄어들고, 반복문의 시간 복잡도는 $T(n) = \Theta(\lfloor\lg n\rfloor)$ , 즉 $\Theta(\lg n)$ 이 됩니다. 이것이 전체 코드 중에 시간 복잡도가 가장 큰 부분이므로, 전체 시간 복잡도 또한 $\Theta(\lg n)$ 이 됩니다.

자바로 구현하기

바이너리 서치의 수도코드는 자바 코드로 이렇게 옮길 수 있습니다. 일단 정수 배열을 받는 것으로 하고, 나중에 제네릭generic 메소드로 확장해보겠습니다.

public class BinarySearchIntArray {
  public static int search(int[] arr, int target) {
    int begin = 0;
    int end = arr.length;
    while (begin < end) {
      int mid = begin + (end - begin) / 2;
      int midVal = arr[mid];

      if (midVal == target) {
        return mid;
      }

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

    return -1;
  }
}

잘 동작하는 지 유닛 테스트로 확인해봅시다. 세 번째 데이터를 찾아 인덱스를 리턴하는 케이스입니다.

  static int[] SORTED = { 10, 20, 30, 40, 50, 60, 70 };

  @Test
  public void testFound() {
    int[] arr = SORTED;
    int valueAt2 = arr[2];

    int index = search(arr, valueAt2);

    assertEquals(2, index);
  }

배열에 없는 데이터를 찾는 데 실패해 -1를 리턴하는 케이스입니다.

  static int BAD_VALUE = 0;

  @Test
  public void testNotFound() {
    int[] arr = SORTED;
    int badValue = BAD_VALUE;

    int index = search(arr, badValue);

    assertEquals(-1, index);
  }

모두 잘 통과하는 케이스입니다.

소요 시간 측정

이렇게 구현한 바이너리 서치의 소요 시간을 배열의 크기 $n$ 에 따라 재봅시다. 정말로 시간 복잡도가 $\Theta(\lg n)$ 를 따른다면, $n$ 이 두 배가 될 때마다 소요 시간은 일정한 간격으로 늘어나야 합니다.

실제 측정한 결과는 이렇습니다.

그림 4. 배열의 크기에 따른 바이너리 서치의 최악의 경우 소요 시간. 직선은 회귀선.

위 그래프에서는 직선으로 보이지만, $n$ 축은 로그 스케일이기 때문에 소요 시간은 $\lg n$ 에 비례합니다. 따라서 시간 복잡도가 $\Theta(\lg n)$ 를 따른다는 실험적인 증거가 됩니다.

순서

바이너리 서치가 똑같은 일을 시퀀셜 서치보다 더 빨리 할 수 있었던 이유는 뭘까요? 둘을 비교하자면, 바이너리 서치에서 특별히 더 확인했던 것은 데이터의 순서 비교였습니다. 그런데 이 순서가 데이터 바깥에서 정할 수 있는 것이라면, 바이너리 서치가 구체적인 순서를 알 필요가 없도록 바꿀 수도 있습니다.

그러면 순서라는 개념을 정의해보고, 이를 이용해 다른 종류의 순서를 바이너리 서치에 적용해보겠습니다.

오더링

사람들을 한 줄로 세워야 한다면, 어떤식으로 하면 좋을까요?

예를 들어, 가나다순, 즉 이름의 사전순lexicographical order으로 할 수 있고, 태어난 날짜로도 할 수 있습니다. 왜냐면 어떤 두 사람이든 그렇게 순서를 비교할 수 있기 때문입니다.

아니면, 부모에서 자식 순은 어떨까요? 그러면 부모와 자식 관계에 있는 사람들은 순서를 가지지만, 그 외의 사람들과는 그렇지 않기 때문에 한 줄로 세울 수 없게 됩니다.

various orderings — 그림 5. 다양한 오더링 예시. 오더링에 따라 사람을 한 줄로 세울 수도 있고, 그럴 수 없기도 합니다.

이 예시로 두 가지 사실을 알 수 있습니다.

순서는 데이터 바깥에서 정할 수 있다. 즉, 같은 데이터는 여러가지의 순서를 가질 수 있다.
모든 데이터가 서로 순서가 정해졌을 때만, 일렬로 놓을 수 있다.

첫 번째 사실에서 정한 순서는 파셜 오더링partial ordering 혹은 그냥 오더링이라고도 부릅니다. 그리고 두 데이터 $a$ , $b\,$ 에 오더링이 있으면 $a \leq b$ 혹은 $a \preceq b$ 로 표현합니다. 가계도 예시의 경우, 부모가 $a$ 이고 자식이 $b$ 인 경우가 이에 해당합니다. 이처럼 두 데이터에 오더링이 있는 경우, 비교 가능하다는 뜻으로 두 데이터가 컴패러블comparable하다고 합니다. 가계도의 경우, 부모 $a$ 는 자식 $b$ 와 컴패러블하지만 그 형제와는 그렇지 않습니다.

만약 두 번째 경우처럼 모든 데이터가 서로 컴패러블하면, 그 오더링은 토탈 오더링total ordering 혹은 리니어 오더링linear ordering이라고 부릅니다. 즉 이름의 사전순과 태어난 날짜순은 토탈 오더링이고, 가계도 순서는 그렇지 않은 파셜 오더링입니다.

일반적인 숫자 비교 $\leq$ 는 대표적인 토탈 오더링입니다. 그렇기 때문에 카드 예시에서 숫자를 비교할 수 있었던 것입니다. 예륻 들어, 다음 숫자들은 $\leq$ 를 따라 소트되어 있습니다.

9 \leq 26 \leq 43 \leq 84 \leq 93 \leq 110

그런데 오더링은 적절한 규칙에 따라 마음대로 만들어낼 수 있습니다. $8$ 로 나눈 나머지의 크기를 비교하는 오더링을 $\leq_8$ 이라고 해봅시다. 예를 들어 $8$ 은 그 나머지가 $1$ 보다 작으므로, $8 \leq_8 1$ 로 쓸 수 있습니다. 그러면 아까 나열한 숫자들이 따르는 또 다른 토탈 오더링이기도 합니다.

\def\remleq{\leq_8} 9 \remleq 26 \remleq 43 \remleq 84 \remleq 93 \remleq 110

이처럼 똑같은 데이터가 다른 토탈 오더링을 가질 수 있다는 것은, 바이너리 서치 구현에서 오더링을 분리할 수 있는 이론적인 이유가 됩니다.

알고리즘에서 오더링 분리하기

바이너리 서치가 구체적인 오더링을 알 필요 없게끔 만들어봅시다. 마침 자바에는 오더링을 위한 Comparator 인터페이스가 내장되어 있습니다. 이를 통해 오더링을 외부에서 받게 만들면, 바이너리 서치는 어떠한 오더링도 가정하지 않게 됩니다.

public class BinarySearchArray {
  public static <T> int search(T[] arr, T target, Comparator<T> comp) {
    int begin = 0;
    int end = arr.length;
    while (begin < end) {
      int mid = begin + (end - begin) / 2;
      T midVal = arr[mid];

      if (isEqualTo(midVal, target, comp)) {
        return mid;
      }

      if (isLessThan(midVal, target, comp)) {
        begin = mid+1;
      } else {
        end = mid;
      }
    }

    return -1;
  }
}

데이터의 타입은 제네릭 타입 T로 확장했습니다. 이 타입은 Comparable 같은 인터페이스를 구현할 필요가 없습니다. (방금의 Comparator와는 다른 것입니다.) 즉 데이터의 타입 자체에 오더링이 있지 않아도 됩니다.

한편, Comparator 인터페이스의 compare() 메소드가 읽기 불편한 감이 있기 때문에, 읽기 쉬운 이름으로 분리했습니다.

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

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

한편, 오더링을 분리하긴 했지만, Comparable 인터페이스로 이미 구현해놓은 오더링을 쓰고 싶은 경우에도 매번 comp 인자를 전달하기는 번거롭습니다. 따라서 편의상 오더링을 생략할 수 있게 오버로딩합시다.

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

    return BinarySearchArray.search(arr, target, identityComp);
  }

데이터 타입 T가 이미 컴패러블할 때 오더링을 생략하면, 자바에서 내츄럴 오더링natural ordering이라고 부르는 기존 오더링을 사용합니다.

이 메소드가 잘 동작하는지 테스트해봅시다. 앞서 예시로 든 오더링 $\leq_8$ 로도 바이너리 서치를 할 수 있습니다. 이를 통해 세 번째 데이터를 찾도록 만듭시다.

  static Integer[] SORTED = { 9, 26, 43, 84, 93, 110 };
  static Comparator<Integer> REM8 = Comparator.comparing(v -> v % 8);

  @Nested
  class Rem8Ordering {
    @Test
    public void testFound() {
      Integer[] arr = SORTED;
      Integer valueAt2 = arr[2];

      int index = search(arr, valueAt2, REM8);

      assertEquals(2, index);
    }
  }

여기서 REM8이 $\leq_8$ 오더링의 구현입니다.

오더링을 생략한 경우를 오버로딩했기 때문에, 수정 전의 인터페이스도 유지합니다.

  @Nested
  class DefaultComparator {
    @Test
    public void testFound() {
      Integer[] arr = SORTED;
      Integer valueAt2 = arr[2];

      int index = search(arr, valueAt2);

      assertEquals(2, index);
    }
  }

오더링과 이퀴밸런스

방금 $\leq_8$ 오더링의 테스트는 세 번째 데이터를 잘 찾습니다. 그런데 사실은 그 숫자 자체를 찾는 것이 아니라, 같은 것으로 취급하는 종류를 찾는 것입니다. 여기선 $8$ 로 나눈 나머지가 같은 것이 그런 종류가 됩니다.

이처럼 오더링은 ‘같다’는 개념을 은연중에 이용합니다. 그 이유는 오더링을 정의할 때 지켜야 하는 세 가지 요소에서 알 수 있습니다.

리플렉시브reflexive: 데이터는 자기 자신과 오더링이 있어야 합니다. 즉, 데이터 $a$ 가 있으면 $a \preceq a$ 이어야 합니다.
안티시메트릭antisymmetric: 두 데이터에 오더링이 있고, 그 반대의 오더링도 있으면, 그 둘은 같아야 합니다. 즉, 데이터 $a$ , $b$ 가 $a \preceq b$ 이고 $b \preceq a$ 이면, $a = b$ 이어야 합니다.
트랜지티브transitive: 데이터 $a$ , $b$ , $c$ 가 $a \preceq b$ 이고, $b \preceq c$ 이면, 반드시 $a \preceq c$ 이어야 합니다.

이해를 위해 숫자의 대소 비교 $\leq$ 로 예를 들어보겠습니다. 이렇게 보면 당연하게 느껴지는 속성입니다.

$1 \leq 1$ 처럼, 숫자는 항상 자기 자신 이상입니다. (리플렉시브)
숫자 $a$ , $b$ 가 $a \leq b$ 이고 $b \leq a$ 이면, $a = b$ 입니다. (안티시메트릭)
숫자 $a$ , $b$ , $c$ 가 $a \leq b$ 이고, $b \leq c$ 이면, $a$ 와 $c$ 는 비교할 필요 없이 $a \leq c$ 입니다. (트랜지티브)

그런데 리플렉시브와 안티시메트릭으로부터, 다음 두 문장이 논리적으로 같은 말logical equilvalence이라는 것을 알게 됩니다.

$a = b$
$a \preceq b$ 이고 $b \preceq a$

앞서 예로 든 오더링 $\leq_8$ 을 봅시다. 그러면 $0 \leq_8 8$ 이기도 하지만, $8 \leq_8 0$ 이기도 합니다. 따라서 $0 = 8$ 이어야 합니다.

이런 결론이 나오는 이유는, $\leq_8$ 은 $8$ 로 나눈 나머지가 같은 숫자를 모두 같은 것으로 취급하기 때문입니다. 이런식으로 정해지는 ‘같다’의 의미를 $=_8$ 로 나타낸다면, 이렇게 표현할 수 있습니다.

\def\remeq{=_8} 0 \remeq 8 \remeq 16 \remeq \dotsb

이처럼 같다는 관계 또한, 동일한 데이터 상에서 얼마든지 새로 만들 수 있습니다. 그리고 그것을 동치 혹은 이퀴밸런스 릴레이션equivalence relation, 아니면 그냥 이퀴밸런스라고 부릅니다. 그러면 이 이퀴밸런스로 같다고 취급하는 것들이 생기는데, 이퀴밸런스 클래스equivalence class라고 합니다.

이퀴밸런스 $=_8$ 은 숫자 중 $0, 8, 16, \dotsc$ 을 하나의 이퀴밸런스 클래스로 만듭니다. 이것을 $[0] = \{ 0,8,16,\dotsc \}$ 로 나타냅시다. 이런 식으로 $[1] = \{1, 9, 17, \dotsc\}$ 을 비롯해 여덟 개의 이퀴밸런스 클래스 $[0], \dotsc, [7]$ 이 만들어집니다.

이처럼 이퀴밸런스는 데이터를 항상 여러 부분으로 쪼개는데, 각 부분을 파티션partition이라고 부릅니다. 각 파티션은 서로 겹치는 부분이 없고, 파티션을 모두 합쳤을 때 데이터 전부를 이룹니다. 즉 $[0], \dotsc, [7]$ 까지의 파티션은 모든 숫자를 여덟 부분으로 나눕니다.

partitions — 그림 6. 이퀴밸런스가 만드는 파티션. 모든 숫자가 여덟 파티션으로 나뉩니다. 각 파티션은 곧 이퀴밸런스 클래스로, 이퀴밸런스가 같은 것으로 취급하는 숫자들입니다.

자바 얘기를 잠깐 하자면, 자바에서 이퀴밸런스는 Object.equals() 같은 메소드가 맡아서, 오더링과 이퀴밸런스가 따로 구현됩니다. 앞서 이론 상 오더링은 그것을 위한 이퀴밸런스를 암묵적으로 가정한다고 했지만, 자바에서는 오더링의 구현과 이퀴밸런스의 구현이 실제론 다른 뜻을 가질 수 있습니다.

순서대로 놓기

카드 $n$ 개가 아무렇게나 있다면, 원하는 카드를 $m$ 번 찾는 일은 시퀀셜 서치를 통해 최악의 경우 $\Theta(mn)$ 의 시간 복잡도를 가집니다. 한편, 카드를 소트해서 바이너리 서치 대신 쓸 수 있으므로, 소팅 알고리즘이 $\Theta(f(n))$ 의 시간이 들면, 전체적인 시간 복잡도는 $\Theta(f(n) + m\lg n)$ 이 됩니다.

그런데 결론부터 얘기하자면, 곧 알아볼 인서션 소트는 최악의 경우 $\Theta(f(n)) = \Theta(n^2)$ 입니다. 즉 소트해놓고 $m$ 번 서치하는 것은 $\Theta(n^2 + m\lg n)$ 의 시간 복잡도를 갖습니다. 따라서 서치 횟수 $m$ 이 카드 개수 $n$ 을 넘을 정도로 많다면, 소트를 해놓는 것이 유리하다는 결론을 낼 수 있습니다.

그러면 간단한 소팅 알고리즘인 인서션 소트를 살펴보겠습니다. 하지만 간단함에 비해 이것이 가지는 중요한 내용은

인서션 소트

인서션 소트는 이름 그대로 데이터를 제자리에 넣는 것입니다.

카드를 예로 들어서, 왼쪽에 소트된 카드를 들고있다고 해봅시다. 카드 한 장은 이미 소트됐다고 볼 수 있으므로, 왼쪽에서 한 장부터 시작합니다. 그리고 오른쪽에서 카드를 하나씩 가져와서, 왼쪽과 차례차례 비교하면서 제자리를 찾습니다.

수도코드로는 이렇게 표현할 수 있습니다.

인서션 소트 ( $\textit{arr}$ , $\textit{begin}$ , $\textit{end}$ ) // 배열 $\textit{arr}\,$ 을 구간 [ $\textit{begin},\textit{end}$ )에서 소트

다음을

\textit{begin}+1

부터

\textit{end}\,

전까지인

i

마다 반복

$j \leftarrow i-1$ // 바로 왼쪽 데이터의 인덱스

// 오른쪽( $j+1$ )이 바로 왼쪽( $j$ )과 자리가 안맞는 동안

다음을

j \geq \textit{begin}

이고

arr[j] > arr[j+1]

인 동안 반복

// 오른쪽은 왼쪽과 자리 바꿈

$\textit{arr}[j]$ 와 $\textit{arr}[j+1]$ 스왑

$j \leftarrow j-1$

이 알고리즘이 올바르다는 사실은 이번에도 루프 인베리언트로 확인할 수 있습니다. 여기서는 왼쪽 부분인 구간 $[0, i)$ 이 반복문 내내 소트되어 있다는 것으로 한다면, 반복문이 끝났을 때 모든 구간이 소트가 되는 것입니다. 이것은 아까와 비슷한 내용이므로 직접 해보는 것으로 남기고 넘어가겠습니다.

시간 복잡도를 계산해봅시다. 먼저 최선의 경우는 이미 소트된 배열일 때인데, 이 경우 스왑은 한 번도 일어나지 않고 반복문은 인덱스 $i$ 를 $n$ 번 증가시킬 뿐이므로, 시간 복잡도는 $\Theta(n)$ 이 됩니다.

최악의 경우는 데이터가 소트할 반대 순서로 있을 때이고, 시간 복잡도는 $\Theta(n^2)$ 가 됩니다. 바깥쪽의 반복문이 $n-1$ 번 반복하는 동안, 안쪽 반복문은 $1, 2, \dotsc, n-1$ 번 반복합니다. 그러면 다음 계산식을 통해 결과를 나타납니다.

1 + 2 + \dots + n-1 = (n-1)n/2 = \Theta(n^2)

인서션 소트의 수도코드 그대로 자바로 구현할 수 있습니다. 여기서는 스트레터지 패턴strategy pattern을 통해, 클래스가 소트에만 집중할 수 있도록 만들겠습니다.

먼저, 각 스트레터지가 만족해야할 인터페이스를 준비합시다. 여기서 Comparator 인스턴스를 받음으로써, 바이너리 서치 때처럼 오더링 구현이 분리됩니다.

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

그리고 인서션 소트를 스트레터지로 구현합니다. 구현은 수도코드를 그대로 옮긴 것입니다.

public class InsertionStrategy<T> implements ArraySortStrategy<T> {
  public T[] sortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    for (int i = begin+1; i < end; ++i) {
      int j = i-1;

      while (j >= begin && isGreaterThan(arr[j], arr[j+1], comp)) {
        swap(arr, j, j+1);
        j--;
      }
    }

    return arr;
  }
}

여기서 isGreaterThan() 메소드는 바이너리 서치 때처럼 분리한 것입니다.

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

사용자가 사용할 소트 메소드는 별도의 스태틱 메소드로 제공합니다. 이를 통해 구체적인 소팅 알고리즘을 스트레터지 인자로 줄 수 있습니다.

public class ArraySorter {
  public static <T> T[] sortArray(T[] arr, int begin, int end, ArraySortStrategy<T> strat, Comparator<T> comp) {
    return strat.sortArray(arr, begin, end, comp);
  }
}

이 메소드가 구간을 생략하면 전체 구간을 소트하도록 오버로딩합시다.

  public static <T> T[] sortArray(T[] arr, ArraySortStrategy<T> strat, Comparator<T> comp) {
    return ArraySorter.sortArray(arr, 0, arr.length, strat, comp);
  }

나아가 오더링도 생략할 수 있도록 오버로딩합니다.

  public static <T extends Comparable<? super T>> T[] sortArray(T[] arr, ArraySortStrategy<T> strat) {
    return ArraySorter.sortArray(arr, 0, arr.length, strat);
  }

이렇게 파라미터의 생략을 구체적인 스트레터지에서가 아닌 ArraySorter라는 별도의 클래스에서 구현했습니다. 따라서 각 스트레터지는 소트하는 방법에만 집중하고, 파라미터를 어떻게 받을 것인지는 신경쓰지 않게 됩니다.

그러면 소팅 알고리즘의 사용자는 이 메소드를 다음 테스트 코드와 같이 사용할 수 있습니다. 즉 toSort 배열과 같은 데이터는 expected 배열처럼 정리됩니다.

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

    ArraySorter.sortArray(toSort, strat);

    assertArrayEquals(expected, toSort);
  }

그리고 앞서 정의한 $\leq_8$ 오더링으로도 소팅이 가능합니다.

  @Test
  public void testRem8DistinctSort() {
    Integer[] toSort = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    Integer[] expected = { 0, 8, 1, 9, 2, 10, 3, 4, 5, 6, 7 };
    ArraySortStrategy<Integer> strat = new InsertionStrategy<>();

    ArraySorter.sortArray(toSort, strat, Comparator.comparing(v -> v % 8));

    assertArrayEquals(expected, toSort);
  }

소요 시간 측정

위에서 분석한 시간 복잡도를 확인해봅시다. 최선의 경우와 최악의 경우에 대해, 배열의 크기를 두 배씩 키우면서 측정한 결과는 다음과 같습니다.

측정 결과 회귀 선에 따르면, 최선의 경우는 대략 $\Theta(n^{1.04})$ , 최악의 경우는 $\Theta(n^{2.07})$ 로 나타납니다. 각 경우는 이론적인 시간 복잡도 $\Theta(n)$ , $\Theta(n^2)$ 의 실험적인 증거로 볼 수 있습니다.

이퀴밸런스 클래스 소팅

아까의 유닛 테스트에서 $\leq_8$ 오더링의 경우, 값 자체가 아니라 이퀴밸런스 클래스를 소팅하는 것입니다. 예를 들어, 이런 테스트 케이스를 만들어봅시다.

  @Test
  public void testRem8DuplicateSort() {
    Integer[] toSort = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    Integer[] expected = { 0, 8, 1, 9, 2, 10, 3, 4, 5, 6, 7 };
    ArraySortStrategy<Integer> strat = new InsertionStrategy<>();

    ArraySorter.sortArray(toSort, strat, Comparator.comparing(v -> v % 8));

    assertArrayEquals(expected, toSort);
  }

이 케이스는 차례대로 있는 숫자를 이상한 순서로 섞는 것처럼 보이지만, 이퀴밸런스 클래스로 구역을 나눠보면 무엇을 소팅한 것인지 분명해집니다.

\begin{array}{cccccccc} \begin{gathered} \undergroup{\mathstrut 0, 8} \\ {\small [0]} \end{gathered} & \begin{gathered} \undergroup{\mathstrut 1, 9} \\ {\small [1]} \end{gathered} & \begin{gathered} \undergroup{\mathstrut 2, 10} \\ {\small [2]} \end{gathered} & \begin{gathered} \undergroup{\mathstrut 3} \\ {\small [3]} \end{gathered} & \begin{gathered} \undergroup{\mathstrut 4} \\ {\small [4]} \end{gathered} & \begin{gathered} \undergroup{\mathstrut 5} \\ {\small [5]} \end{gathered} & \begin{gathered} \undergroup{\mathstrut 6} \\ {\small [6]} \end{gathered} & \begin{gathered} \undergroup{\mathstrut 7} \\ {\small [7]} \end{gathered} \end{array}

여기서 $0$ 과 $8$ 은 소팅 전의 순서가 후에도 유지됐고, $1$ 과 $9$ , $2$ 와 $10$ 도 마찬가지입니다. 이렇게 소팅 전의 순서가 유지되는 소팅 알고리즘을 안정적 혹은 스테이블stable하다고 부릅니다. 즉 인서션 소트는 스테이블합니다.

이런 스테이블함을 어떻게 이용할 수 있을까요? 예를 들어, 동물병원에 이런 문제가 있다고 상상해봅시다.

동물병원에서 진찰 기록이 실수로 섞여버렸습니다. 고양이 기록은 이름 순으로, 강아지 기록은 섞인 순서를 유지해야 합니다. 그리고 고양이 기록은 강아지 기록 다음에 와야합니다.

animal records — 그림 9. 동물 진찰 기록. 왼쪽처럼 섞인 것을 오른쪽처럼 정리해야 합니다. 강아지 기록은 섞인 순서를 유지하고, 고양이 기록은 이름순으로 소트합니다.

간단한 해결 방법으로는, 하나하나 기록을 확인하며 강아지와 고양이 기록으로 분리한 다음, 고양이 기록을 소트하고, 이걸 강아지 기록 뒤에 놓으면 될 것 같습니다. (간단하다고 했는데 설명하고 보니 복잡하긴 하네요.)

그런데 오더링을 잘 정해주면 한 번의 소트로 해결할 수 있습니다. 두 기록을 비교할 때, 한쪽이 강아지면 종에 따라, 둘 다 고양이면 이름순으로 순서를 줍시다. 종에 따른 오더링은 강아지 $\preceq$ 고양이와 같이 정합시다.

동물 오더링 ( $\textit{animal\,}_1, \textit{animal\,}_2$ )

만약

\textit{animal\,}_1

이나

\textit{animal\,}_2

이 강아지이면

리턴 종 오더링(

\textit{animal\,}_1

의 종,

\textit{animal\,}_2

의 종)

// 둘 다 고양이면

리턴 이름 오더링(

\textit{animal\,}_1

의 이름,

\textit{animal\,}_2

의 이름)

이 오더링은 강아지 기록을 전부 같은 것, 즉 이퀴밸런스 클래스로 취급합니다. 그러면 스테이블 소팅 알고리즘은, 강아지 기록의 순서를 바꾸지 않습니다. 그리고 강아지가 $\preceq$ 고양이라고 했으므로, 강아지 기록은 배열 왼쪽으로 몰게됩니다.

테스트로 확인해봅시다. 먼저, 동물 기록 클래스를 간단히 준비합니다.

  class AnimalRecord {
    public String species;
    public String name;

    public AnimalRecord(String species, String name) {
      this.species = species;
      this.name = name;
    }
  }

그리고 테스트 케이스에서 동물 기록들을 초기화합시다.

  @Test
  public void testAnimalRecordSort() {
    final AnimalRecord[] recs = {
      new AnimalRecord("Dog", "3"),
      new AnimalRecord("Dog", "2"),
      new AnimalRecord("Dog", "1"),
      new AnimalRecord("Cat", "A"),
      new AnimalRecord("Cat", "B"),
      new AnimalRecord("Cat", "C"),
    };

    // ...
  }

앞서 들었던 예시는 이렇게 표현할 수 있습니다.

    AnimalRecord[] toSort = { recs[0], recs[5], recs[3], recs[1], recs[4], recs[2] };
    AnimalRecord[] expected = recs;

본격적인 테스트 내용은 앞서 설명한 오더링으로 소트하는 것입니다.

    ArraySortStrategy<AnimalRecord> strat = new InsertionStrategy<>();

    ArraySorter.sortArray(toSort, strat, (rec1, rec2) -> {
      int speciesOrder1 = rec1.species.equals("Dog") ? 0 : 1;
      int speciesOrder2 = rec2.species.equals("Dog") ? 0 : 1;

      if (speciesOrder1 == 0 || speciesOrder2 == 0) {
        return speciesOrder1 - speciesOrder2; // follow species ordering
      }

      return rec1.name.compareTo(rec2.name);
    });

    assertArrayEquals(expected, toSort);

잘 통과하는 테스트로서 동물병원 문제를 해결됐습니다.

여기까지 읽으셨다면 이 문제에 도전해보세요.

숫자 중에 홀수를 왼쪽으로, 짝수를 오른쪽으로 분리하려고 합니다. 예를 들어, $1$ , $4$ , $2$ , $3$ 과 같이 있다면, $1$ , $3$ , $4$ , $2$ 와 같은 식입니다. 어떤 오더링으로 소팅 알고리즘을 만들 수 있을까요?

한 번에 많이 정리하기

데이터가 얼마나 섞여있는가의 기준을 세우고나면, 소팅 알고리즘이 얼마나 빨리 소트하는가도 말할 수 있게 됩니다. 이를 통해 인서션 소트가 얼마나 천천히 데이터를 정리하는지 알아보고, 데이터를 ‘한 번에 많이’ 소트하도록 바꿔보겠습니다.

인버전

오더링을 따르지 않는 두 데이터를 인버전inversion이라고 부릅니다.

inversion diagram — 그림 10. 인버전 다이어그램. 예를 들어 크기 순을 따르지 않는 두 숫자가 인버전이 됩니다.

곧 보겠지만, 인서션 소트의 시간 복잡도는 인버전의 개수에 직접적으로 영향을 받습니다. 그러면 인버전은 몇 개까지 될 수 있을까요?

인버전이 가장 적을 때는 데이터가 이미 소트되었을 때이고, 개수는 $0$ 개가 됩니다.
인버전이 가장 많을 때는 데이터가 오더링의 반대로 소트된 경우입니다. 이 때의 인버전 개수는 첫 번째 데이터부터 직접 세보면, $n-1$ 부터 $1$ 까지의 합인 $\sum_{k=1}^{n-1} k$ , 즉 $n(n-1)/2$ 가 됩니다.

number of inversions — 그림 11. 인버전의 최대 개수. 데이터가 반대로 소트되어 있을 때, 첫 번째 데이터와 이루는 인버전부터 세봄으로써 모든 인버전의 개수를 구할 수 있습니다.

인서션 소트는 인접한 두 데이터가 인버전일 때마다 스왑합니다. 그리고 인접한 인버전을 해소할 때마다, 총 인버전 개수는 하나씩 줄어듭니다. (증명은 간단하니 직접 해보는 것으로 남기겠습니다.) 따라서 인서션 소트가 스왑하는 횟수는 정확히 인버전의 개수와 같게 됩니다.

인버전의 개수를 데이터가 ‘섞인 정도’라고 해봅시다. 그러면 인서션 소트의 스왑 횟수는 데이터가 섞인 정도에 비례한다고 볼 수 있습니다. 따라서 인서션 소트란 거의 섞이지 않은 데이터일 수록 빠른 소팅 알고리즘이 됩니다.

인버전을 통해 시간 복잡도를 다시 구해봅시다. 최선의 경우, 배열이 소트되어 있더라도 알고리즘은 각 데이터를 확인하기 때문에, 적어도 $\Theta(n)$ 의 시간이 필요합니다. 하지만 인버전이 없기 때문에 스왑은 없습니다. 따라서 시간 복잡도는 그대로 $\Theta(n)$ 입니다.

최악의 경우, 인버전 개수는 앞서 구했듯 $n(n-1)/2 = \Theta(n^2)$ 개입니다. 따라서 같은 결과인 $\Theta(n^2)$ 이 다시 나타나게 됩니다.

평균의 경우, 먼저 입력값의 분포를 가정해야 시간 복잡도를 말할 수 있습니다.

각 인버전 개수가 같은 확률로 등장한다고 가정해봅시다. 그 개수는 평균적으로 $n(n-1)/4$ 개임이 알려져 있기 때문에, 최악의 경우처럼 $\Theta(n^2)$ 가 됩니다.
평균적으로 거의 소트된 데이터가 존재한다고 가정하면, 최선의 경우처럼 $\Theta(n)$ 에 가까울 것입니다.

정리하면, 인서션 소트는 대체로 $\Theta(n^2)$ 의 시간이 들지만, 거의 소트된 경우에는 $\Theta(n)$ 의 시간이 듭니다.

한 번에 많은 인버전 줄이기

한 번의 스왑에 하나의 인버전만 줄이는 인서션 소트처럼 말고, 여러 개의 인버전을 줄인다면 소팅이 빨라지지 않을까요?

인버전인 $i$ 번째와 $j$ 번째 데이터를 간단히 $(i, j)$ 로 나타낸다면, 인서션 소트는 $(i, i+1)$ 꼴의 인버전만 해소하는 것입니다. 그런데 만약 대신 $(i, i+2)$ 처럼 두 칸 떨어진 인버전을 해소한다고 해봅시다. 이 경우 최소 하나에서 최대 세 개의 인버전이 해소됩니다. 사실 $n$ 칸이 떨어진 인버전을 해소하면, 최대 $2n-1$ 개의 인버전이 줄어듭니다. (직접 계산해보세요.)

따라서 $h$ 만큼 멀리 떨어진 인버전 $(i, i+h)$ 부터 해소한다면, 인서션 소트보다 한 번에 많이 인버전을 줄이므로, 스왑 횟수 또한 줄일 수 있을 것입니다. 그렇다면 이렇게 소트하는 알고리즘을 만들어보면 어떨까요?

그런 알고리즘으로 셸 소트Shell sort라는 알고리즘이 있습니다. 이 알고리즘의 동작 방식을 설명하기 위해 몇 가지 용어를 정리하고 넘어가보겠습니다.

배열 중에 $h$ 만큼 떨어진 데이터를 모아서 서브 배열을 만들어본다면, 배열은 총 $h$ 개의 서브 배열로 나눠집니다. 그러면 $(i, i+h)$ 의 인버전을 해소한다는 것은 서브 배열에서 인서션 소트를 하는 것입니다. 만약 각각의 서브 배열이 소트되었다면, 전체 배열을 $h$ -소트되었다고 부릅니다.

셸 소트란 처음에 큰 $h$ 로 시작해 $h$ -소트하고, $h$ 가 $1$ 이 될 때까지 $h$ 를 줄여가며 반복하는 것입니다.

h-sorted array — 그림 12. 셸 소트. 처음에는 간격이 4인 서브 배열을 소트하고, 다음에는 2로 줄인 간격으로 반복합니다.

여기서 $h=1$ 인 마지막 경우는 인서션 소트를 수행하는 것과 똑같습니다. 따라서 이 소팅 알고리즘은 올바르다는 것을 알 수 있습니다.

셸 소트의 시간 복잡도는 간격 $h$ 를 어떻게 정하느냐에 달려있는데, 그 분석은 어려운 경우가 많습니다. 여기서는 $h = 1, 4, 13, \dotsc, \lfloor n/3 \rfloor$ 로 하고, 시간 복잡도 계산은 생략하겠습니다. 그러면 수도코드로는 이렇게 표현할 수 있습니다.

셸 소트 ( $\textit{arr}$ , $\textit{begin}$ , $\textit{end}$ ) // 배열 $\textit{arr}\,$ 에서 구간 [ $\textit{begin},\textit{end}$ )의 데이터 소트

// 첫 갭

h = \lfloor n/3 \rfloor

을 구함

$h \leftarrow 1$

다음을

h < \lfloor(\textit{end}-\textit{begin})/3\rfloor

인 동안 반복

$\textit{h} \leftarrow 3\textit{h} + 1$

다음을

\textit{h} \geq 1

인 동안 반복

// $h$ -소트, 즉 간격 $\textit{h}\,$ 으로 서브 배열을 인서션 소트

다음을

\textit{begin}+\textit{h}\,

부터

\textit{end}\,

전까지인

i

마다 반복

$j \leftarrow i-\textit{h}$ // 서브 배열 상 바로 왼쪽 데이터 인덱스

// 오른쪽( $j+h$ )과 바로 왼쪽( $j$ )이 인버전인 동안

다음을

j \geq \textit{begin}

이고

arr[j] > arr[j+\textit{h}]

인 동안 반복

// 오른쪽은 왼쪽과 자리 바꿈

\textit{arr}[j]

와

\textit{arr}[j+\textit{h}]

스왑

$j \leftarrow j-\textit{h}$

$\textit{h} \leftarrow \lfloor\textit{h} / 3\rfloor$

셸 소트는 인서션 소트를 일반화한 것으로 생각할 수 있지만, 인서션 소트와는 달리 스테이블하지 않습니다. 그리고 이미 소트된 배열을 소트하는 최선의 경우엔, 셸 소트는 여러 차례 $h$ -소트를 무의미하게 반복하기 때문에, 인서션 소트보다 조금 불리한 시간 복잡도를 가집니다.

구현 및 소요 시간 측정

셸 소트 또한 스트레터지의 구현으로 하겠습니다. 거의 수도코드를 그대로 옮기는 수준으로 만들 수 있습니다.

public class ShellStrategy<T> implements ArraySortStrategy<T> {
  public T[] sortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    int h = 1;
    while (h < (end - begin) / 3) {
      h = 3*h + 1;
    }

    while (h >= 1) {
      for (int i = begin+h; i < end; ++i) {
        int j = i - h;
        while (j >= begin && isGreaterThan(arr[j], arr[j+h], comp)) {
          swap(arr, j, j+h);
          j -= h;
        }
      }

      h /= 3;
    }

    return arr;
  }
}

그리고 소요 시간을 측정해 인서션 소트와 비교하면 이렇습니다.

측정 결과를 통해, 셸 소트는 최선의 경우엔 인서션 소트보다 조금 불리하지만, 최악의 경우는 유리함을 확인할 수 있습니다.

마치며

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

레퍼런스

Introduction to Algorithms (3rd ed., Thomas Cormen et al., 2009)
Algorithms (4th ed., Robert Sedgewick, 2011), 또는 알고리즘 (길벗, 2018)
Programming Pearls (2nd ed., Jon Bentley, 2000), 또는 생각하는 프로그래밍 (인사이트, 2013): 바이너리 서치의 루프 인베리언트 설명.
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): 인버전의 평균 개수 참고.
Introduction to Set Theory (3rd ed., Karel Hrbacek, Thomas Jech, 1999)
Nearly All Binary Searches and Mergesorts are Broken (Joshua Bloch, 2006)
Comparable (Oracle): 토탈 오더링, 내츄럴 오더링과 Comparable 인터페이스의 관계
Object.equals() (Oracle): 이퀴밸런스 릴레이션과 equals() 메소드의 관계.
Reorder Data in Log Files (Leetcode): 본문에서 동물 병원 문제로 언급한 것과 같은 문제.