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

이 카드가 어떻게 분포되어 있는지 모른다면, 원하는 카드를 찾기 위해선 하나하나 뒤집어보는 수밖에 없습니다. 이런 방법은 시퀀셜 서치sequential search, 또는 리니어 서치linear search라고 부릅니다. 모든 데이터가 $n$ 개를 확인해봐야 하는 최악의 경우, 이 알고리즘은 $\Theta(n)$의 시간 복잡도를 가집니다.

한편, 데이터가 분포된 특징을 안다면 이를 서치에 이용할 수 있습니다. 그 중에는 이런 것이 있습니다.

1. 데이터 상에서 순서를 말할 수 있을 때

2. 데이터가 그 순서대로 있을 때

첫 번째는 데이터 상에 오더링ordering이 있다고도 말합니다. 그리고 그런 데이터를 그 순서에 따라 정리하는 것을, 데이터를 정렬 혹은 소트sort한다고 말하고, 그 알고리즘을 소팅 알고리즘sorting algorithm이라고 부릅니다.

데이터가 소트되어 있다는 걸 안다면, 원하는 것을 찾는 문제는 빠르게 해결할 수 있게 됩니다. 바이너리 서치binary search라는 알고리즘은 데이터가 순서대로 있다는 사실을 서치에 활용해서, 최악의 경우에도 $\Theta(\lg n)$의 시간으로 해결하기 때문입니다. 이것이 첫 번째로 알아볼 알고리즘입니다.

반면, 데이터가 소트되어 있는지 모른다면, 매번 시퀀셜 서치를 해야할 것입니다. 하지만 데이터를 소트하고 나면 더 빠른 바이너리 서치를 활용할 수 있게 됩니다. 따라서 소팅은 알고리즘 분야에서 중요한 문제가 됩니다.

소팅에도 다양한 알고리즘이 있지만, 여기서는 간단한 방법인 삽입 정렬 혹은 인서션 소트insertion sort라는 것을 알아보겠습니다. 이것이 두 번째로 알아볼 알고리즘입니다. 여기선 이 알고리즘이 어떤 경우에 느린지 분석해보고, 이를 바탕으로 셸 소트Shell sort 알고리즘으로 개선해보겠습니다.

이번에도 이전 글처럼 다른 라이브러리의 도움없이 처음부터 구현해봅니다.

순서를 이용한 서치

카드가 순서대로 있다는 걸 안다면, 항상 가운데를 확인하는 것이 좋은 전략이 됩니다.

예를 들어 숫자 8을 찾는다고 해봅시다. 그 중 가운데 카드가 6이라면, 이전의 카드는 볼 필요가 없으므로 버립니다. 그리고 숫자 8을 찾을 때까지, 남은 반으로 이를 반복합니다.

서치 구간을 표현하기 위해 양 끝을 나타낼 필요가 있는데요. 여기선 구간의 시작은 $\textit{begin}\,$이, 마지막은 $\textit{end}\,$가 나타냅니다. 다만 $\textit{end}\,$는 마지막 데이터의 다음을 가리킵니다.

이와 같이 마지막이 제외된 구간을 반열린구간half-open interval이라고 부르고 $[\textit{begin}, \textit{end})$로 표현합니다. 이렇게 하면, 구간이 비었다는 사실은 $\textit{begin} = \textit{end}\,$로 표현할 수 있습니다. 반대로, $\textit{begin} < \textit{end}\,$은 구간이 비어있지 않다는 사실을 표현합니다.

이 아이디어를 배열에 있는 데이터에 적용해본다면, 이런 수도코드로 정리해볼 수 있습니다.

$\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}\,$의 초기화와 반복문의 조건도 바뀌어야 하는데요. 이는 직접 해보는 문제로 남겨두겠습니다.

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

존 벤틀리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라고도 불립니다.

첫 번째로, 시작 직전을 봅시다. 이때 수행된 수도코드는 이렇습니다.

서치 대상이 배열에 있다면, 그 인덱스 $i$는 당연히 $0 \leq i < \textit{arr}\,$의 크기입니다. 그리고 수도코드의 변수 초기화로 인해, 루프 인베리언트의 부등식 $\textit{begin} \leq i < \textit{end}\,$가 반복문 시작 직전에 성립합니다.

두 번째로, 반복할 때를 봅시다. 즉 $\textit{begin} < \textit{end}\,$일 때입니다. 가운데 데이터가 서치 대상보다 작다고 해봅시다. 그러면 더 작은 쪽은 볼 필요가 없게 됩니다. 즉 $i$는 큰 쪽 절반 구간 $[\textit{mid}+1, \textit{end})$에 있는 것입니다. 이 때 이런 수도코드가 수행됩니다.

이는 다음 서치 구간을 $[\textit{mid}+1, \textit{end})$로 줄인 것이고, 정확히 $i$가 속하는 구간과 같습니다. 따라서 다음 반복의 시작까지 루프 인베리언트가 성립하게 됩니다. 그리고 반대의 경우, 즉 $i$가 다른 쪽에 속할 때도 이와 비슷하게 할 수 있습니다.

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

결론적으로 루프 인베리언트, 즉 서치 대상이 배열에 있다면 인덱스가 $[\textit{begin}, \textit{end})$ 안에 있음을 보였습니다. 이로부터 반복 조건과 반복마다 줄이는 구간을 올바르게 정했다는 걸 알 수 있게 됩니다. 반대로 이 두 가지가 살짝이라도 달라졌을 때, 루프 인베리언트는 성립하지 않게 되고, 알고리즘은 동작하지 않습니다. (확인해보세요.)

정수 오버플로우 버그

방금 수도코드가 올바르게 동작한다는 것을 확인했지만, 사실 작은 버그를 하나 고쳐야 합니다. 가운데 인덱스를 구하는 부분입니다.

이렇게 더하기를 먼저하면, 숫자가 큰 경우 정수 오버플로우integer overflow를 일으킬 수 있기 때문입니다. 이 글에 따르면 자바Java 라이브러리의 바이너리 서치에도 9년 가까이 있었던 이 버그는, 뺄셈을 대신 이용해 고칠 수 있습니다.

이 뺄셈은 큰 쪽에서 작은 쪽을 빼기 때문에, 오버플로우가 일어나지 않게 됩니다. 비록 오버플로우를 일으킬 만큼 많은 데이터를 여기선 테스트하지 않겠지만, 원칙적으로는 해결한 셈입니다.

시간 복잡도 분석

시간 복잡도는 수행한 수도코드 줄의 개수라고 하고, 크기가 $n$인 배열이 주어졌다고 합시다. 최선의 경우는, 서치 대상이 마침 가운데에 있어서 바이너리 서치가 한 번의 확인으로 끝날 때입니다. 크기와 상관 없이 끝나므로 시간 복잡도는 $\Theta(1)$가 됩니다.

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

이를 반복 적용하면 $\Theta(\lg n)$을 얻을 수 있습니다.

사실 이것은 부분적인 해답인데요. $n$이 $1, 2, 4, 8, \dots$인 경우를 구한 것입니다. 그래서 $T(n/2)$ 항이 $T(1)$로 이어질 수 있었습니다.

일반적인 $n$의 경우, 실제론 구간이 $\lfloor n/2 \rfloor$만큼 줄어들므로, 점화식은 이렇습니다.

그러면 이 점화식을 반복 적용했을 때 $\Theta(1)$가 몇 개인지 문제가 됩니다.

그 개수는 다음과 같이 트리를 그려보면, $\lfloor\lg n \rfloor$임을 알 수 있습니다. 구간의 개수를 이진수로 나타냈을 때, 구간이 줄어들 때마다 라이트 시프트right shift 연산을 하는 것과 같기도 합니다.

따라서 구간은 $\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;
  }
}

잘 동작하는 지 유닛 테스트로 확인해봅시다. 다음과 같이 JUnit 5 프레임워크로 테스트 케이스를 작성해볼 수 있습니다. arr 배열에서 세 번째 데이터를 찾아 인덱스를 리턴하는 케이스입니다.

public class BinarySearchIntArrayTest {
  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를 리턴하는 케이스입니다.

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

    int index = search(arr, badValue);

    assertEquals(-1, index);
  }

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

소요 시간 측정

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

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

순서

바이너리 서치가 똑같은 일을 시퀀셜 서치보다 더 빨리 할 수 있었던 것은, 데이터의 순서를 비교할 수 있었기 때문이라고 할 수 있습니다. 그런데 이 순서가 데이터 바깥에서 정할 수 있는 것이라면, 바이너리 서치를 비롯한 알고리즘은 구체적인 순서를 알 필요가 없게 만들 수 있습니다.

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

오더링

사람들을 한 줄로 세워야 한다고 해봅시다. 예를 들면 이름의 사전순lexicographical order으로 할 수 있습니다. 아니면 태어난 날짜도 가능합니다. 왜냐면 어떤 두 사람든 순서를 그렇게 비교할 수 있기 때문입니다.

한편, 부모에서 자식 순으로, 즉 가계도로 두 사람의 순서를 비교할 수도 있습니다. 그러면 부모와 자식 관계로 이어진 사람들, 즉 직계에서는 순서를 가집니다. 하지만 그 외의 사람들과는 그렇지 않기 때문에, 이 기준으로는 한 줄로 세울 수 없게 됩니다.

이 예시로 두 가지를 알 수 있습니다.

1. 순서는 데이터 바깥에서 정할 수 있다. 즉, 같은 데이터는 여러가지의 순서를 가질 수 있다.

2. 각 데이터가 나머지와 순서가 정해졌을 때만, 데이터를 일렬로 놓을 수 있다.

첫 번째 경우는 파셜 오더링partial ordering 혹은 간단히 오더링을 정의했다고도 말하고, 두 데이터 $a$, $b\,$에 오더링이 있으면 $a \leq b$ 혹은 $a \preceq b$로 표현합니다. 가계도 예시의 경우, 부모가 $a$이고 자식이 $b$인 경우가 이에 해당합니다.

이처럼 두 데이터에 오더링이 있는 경우, 비교 가능하다는 뜻으로 두 데이터가 컴패러블comparable하다고 합니다. 가계도의 경우, 부모 $a$는 자식 $b$와 컴패러블하지만 그 형제와는 그렇지 않습니다.

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

일반적인 숫자 비교 $\leq$는 대표적인 토탈 오더링입니다. 다음 숫자들은 이를 따라 소트되어 있습니다.

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

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

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

바이너리 서치가 구체적인 오더링을 알 필요 없게끔 만들어봅시다. 마침 자바에는 오더링을 위한 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;
  }
}

제너릭generic 타입 T로 확장했습니다. 이 타입은 Comparable 같은 인터페이스를 구현할 필요가 없습니다. 즉 데이터의 타입 자체에 오더링이 있지 않아도 됩니다. 왜냐면 오더링을 밖에서 정하기 때문에, 데이터 자체가 컴패러블한지 알 필요가 없기 때문입니다.

한편, 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;
  }
}

한편, 오더링을 분리하긴 했지만, 특별한 오더링이 필요없을 때도 매번 인자로 전달해야 하는 것은 번거롭습니다. 따라서 편의 상 오더링을 생략할 수 있게 오버로딩overloading합시다.

  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이라고 부르는, 그 타입의 기존 오더링을 사용합니다.

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

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

  @Nested
  class WithRem8Ordering {
    @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 WithoutComparator {
    @Test
    public void testFound() {
      Integer[] arr = SORTED;
      Integer valueAt2 = arr[2];

      int index = search(arr, valueAt2);

      assertEquals(2, index);
    }
  }

오더링과 이퀴밸런스

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

이처럼 오더링은 같다는 의미를 은연중에 이용합니다. 그런데 오더링을 정의하는 요소에서 그 이유를 알 수 있습니다. 오더링은 아무렇게나 만들 수 있지만 적어도 다음 세 가지를 지켜야합니다.

1. 리플렉시브reflexive: 데이터는 자기 자신과 오더링이 있어야 합니다. 즉, 데이터 $a$가 있으면 $a \preceq a$이어야 합니다.

2. 안티시메트릭antisymmetric: 두 데이터에 오더링이 있고, 그 반대의 오더링도 있으면, 그 둘은 같아야 합니다. 즉, 데이터 $a$, $b$가 $a \preceq b$이고 $b \preceq a$이면, $a = b$이어야 합니다.

3. 트랜지티브transitive: 데이터 $a$, $b$, $c$가 $a \preceq b$이고, $b \preceq c$이면, 반드시 $a \preceq c$이어야 합니다.

일반적인 숫자의 대소 비교 $\leq$를 떠올려보면 당연한 사실입니다.

1. $1 \leq 1$처럼, 숫자는 항상 자기 자신 이상입니다. (리플렉시브)

2. 숫자 $a$, $b$가 $a \leq b$이고 $b \leq a$이면, $a = b$입니다. (안티시메트릭)

3. 숫자 $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}$로 쓴다면, 이렇게 표현할 수 있습니다.

이처럼 같다는 관계 또한, 동일한 데이터 상에서 얼마든지 새로 만들 수 있습니다. 이를 동치 혹은 이퀴밸런스 릴레이션equivalence relation, 아니면 간단히 이퀴밸런스라고 부릅니다. 그러면 이 이퀴밸런스로 같다고 취급하는 것들이 생깁니다. 이를 이퀴밸런스 클래스equivalence class라고 합니다. 이 이퀴밸런스는 데이터를 항상 여러 부분으로 쪼갭니다. 이를 파티션partition이라고 합니다. 각 파티션은 서로 겹치는 부분이 없고, 파티션을 모두 합쳤을 때 데이터 전부를 이룹니다.

이퀴밸런스 $=_{{}/8}$은 숫자 중 $0, 8, 16, \dotsc$을 하나의 이퀴밸런스 클래스로 만듭니다. 이를 $[0] = \{ 0,8,16,\dotsc \}$로 표현합시다. 이런 식으로 $[1] = \{1, 9, 17, \dotsc\}$을 비롯해 여덟 개의 이퀴밸런스 클래스 $[0], \dotsc, [7]$이 만들어지고, 이는 모든 숫자를 여덟 부분으로 나누는 파티션이 됩니다.

정리하면 오더링 $\leq_{{}/8}$은 이퀴밸런스 $=_{{}/8}$을 가정합니다.

한편, 자바에서는 오더링과 이퀴밸런스가 따로 구현됩니다. 이퀴밸런스는 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) < \Theta(mn)$으로서 더 나은 시간 복잡도를 가지기 때문입니다.

그러면 소팅 알고리즘 중 간단한 것으로서 인서션 소트insertion sort를 살펴보겠습니다.

인서션 소트

카드를 소트해야 한다고 해봅시다.

카드를 두 부분으로 나눠, 왼쪽 부분이 이미 소트된 부분이라고 합시다. 사실 카드 한 장은 이미 소트되어 있다고 할 수 있습니다. 따라서 소트된 부분은 가장 왼쪽 한 개부터 시작합니다.

인서션 소트는 소트되지 않은 나머지 오른쪽에서 하나씩 가져와 소트된 자리에 넣는 방법입니다. 이때 오른쪽에서 가져온 카드는 바로 왼쪽의 카드와 비교하면서 제자리를 찾습니다.

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

이 알고리즘이 올바르다는 사실은, 왼쪽 부분인 구간$[0, i)$이 소트되어 있다는 루프 인베리언트로 확인할 수 있습니다. 이는 아까와 비슷한 내용이므로 직접 해보는 것으로 남기고 생략하겠습니다.

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

최악의 경우는 데이터가 반대 순서로 있을 때이고, 시간 복잡도는 $\Theta(n^2)$가 됩니다. 바깥쪽 반복문이 반복할 때마다, 안쪽 반복문은 $1, 2, \dotsc, 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라는 별도의 클래스에서 구현했습니다. 따라서 각 스트레터지는 소트하는 방법에만 집중하고, 파라미터를 어떻게 받을 것인지는 신경쓰지 않게 됩니다.

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

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

    ArraySorter.sortArray(unsorted, strat);

    assertArrayEquals(expected, unsorted);
  }

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

  @Test
  public void testRem8DistinctSort() {
    Integer[] unsorted = { 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(unsorted, strat, Comparator.comparing(v -> v % 8));

    assertArrayEquals(expected, unsorted);
  }

소요 시간 측정

위에서 분석한 시간 복잡도를 확인해봅시다. 배열의 크기를 두 배씩 늘이면서 측정한 소요 시간입니다. 최선의 경우와 최악의 경우를 가정하면 다음과 같습니다.

데이터 간에 선형적인 관계가 나타납니다. 측정 데이터로 구한 회귀 선은, 최선의 경우는 대략 $\Theta(n^{1.04})$이고, 최악의 경우는 $\Theta(n^{2.07})$입니다. 이는 각 경우 분석했던 이론적인 시간 복잡도 $\Theta(n)$, $\Theta(n^2)$의 실험적인 증거로 볼 수 있습니다.

이퀴밸런스 클래스 소팅

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

  @Test
  public void testRem8DuplicateSort() {
    Integer[] unsorted = { 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(unsorted, strat,
      Comparator.comparing(v -> v % 8));

    assertArrayEquals(expected, unsorted);
  }

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

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

이런 스테이블함을 어떻게 이용할 수 있을까요? 예를 들어, 동물병원에 이런 문제가 있다고 상상해봅시다. 강아지와 고양이를 진찰한 기록이 섞어버려서 다시 정리해야 합니다.

이 때, 고양이 기록들은 이름 순서대로 다시 정리해야 하고, 강아지 기록들 간에는 섞인 순서를 유지해야 합니다. 이렇게 정리한 기록은 고양이 기록을 강아지 기록 뒤에 두어야 합니다.

간단한 해결 방법으로는, 하나하나 기록을 확인하며 강아지와 고양이 것으로 분리한 다음, 고양이 기록을 소트하고, 이걸 강아지 기록 뒤에 놓으면 될 것 같습니다.

그런데 오더링을 잘 정해주면 한 번의 소트로 해결할 수 있습니다. 둘 중 하나가 강아지면 종에 따라, 둘 다 고양이면 이름에 따라 순서를 줍시다. 종에 따른 오더링은 강아지 $\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[] unsorted = { recs[0], recs[5], recs[3], recs[1], recs[4], recs[2] };
    AnimalRecord[] expected = recs;

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

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

    ArraySorter.sortArray(unsorted, 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, unsorted);

이는 잘 통과하는 테스트입니다. 따라서 동물병원 문제를 해결했습니다.

여기까지 읽으셨다면 이 문제에 도전해보세요. 만약 배열에 숫자가 있고, 홀수를 배열 왼쪽으로, 짝수를 나머지 오른쪽으로 오게끔 분리하고 싶다면 어떻게 해야 할까요? 즉 예를 들어 배열에 숫자가 $1, 4, 2, 3$과 같이 있다면, $1, 3, 4, 2$와 같이 홀수와 짝수를 양쪽으로 분리해야 합니다.

한 번에 많이 정리하기

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

인버전

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

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

• 인버전이 가장 적을 때는 데이터가 이미 소트되었을 때이고, 개수는 $0$ 개가 됩니다.

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

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

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

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

최악의 경우, 인버전 개수는 앞서 구했듯 $n(n-1)/2 = \Theta(n^2)$ 개인데요. 이것은 각 데이터를 확인하는 데 드는 시간 복잡도 $\Theta(n)$보다 크기 때문에, 시간 복잡도는 $\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)$부터 해소한다면, 인서션 소트보다 한 번에 많이 인버전을 줄이므로, 스왑 횟수 또한 줄일 수 있을 것입니다.

$h$ 만큼 떨어진 데이터만 모아서 하나의 서브 배열로 바라봅시다. 전체 배열은 이런 서브 배열이 $h$ 개 존재합니다. 서브 배열에서 인서션 소트를 하는 것은, 곧 $(i, i+h)$의 인버전을 해소하는 것입니다. 그리고 이렇게 소트된 배열을 $h$-소트되었다고 부릅니다.

처음에 큰 $h$로 시작해 $h$-소트하고, $h$가 $1$이 될 때까지 더 작은 $h$로 이를 반복하는 것을 셸 소트Shell sort라고 부릅니다. 여기서 마지막 경우는 인서션 소트를 수행하는 것과 똑같습니다. 따라서 적어도 마지막 경우 때문에, 이 소팅 알고리즘이 올바르다는 것을 알 수 있습니다.

셸 소트의 시간 복잡도는 간격 $h$를 어떻게 정하느냐에 달려있습니다. 그리고 보통은 분석이 어렵습니다. 여기서는 $h = 1, 4, 13, \dotsc, \lfloor n/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;
  }
}

이렇게 구현한 셸 소트는, 다음 테스트 코드처럼 스트레터지를 넘겨줌으로써 사용할 수 있습니다.

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

    ArraySorter.sortArray(unsorted, strat);

    assertArrayEquals(expected, unsorted);

이 코드를 바탕으로 소요 시간을 측정해 인서션 소트와 비교하면 이렇습니다.

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

마치며

순서는 바이너리 서치와 소팅 알고리즘이 의존하는 개념입니다. 이퀴밸런스와 오더링이라는 개념을 통해, 각각 같음과 순서는 데이터 바깥에서 정해질 수 있다는 것을 살펴봤습니다. 그리고 이를 통해 바이너리 서치와 인서션 소트가 데이터의 순서를 신경쓰지 않도록 구현할 수 있었습니다. 이는 하나의 알고리즘이 다양한 오더링에 따라 수행을 하도록 만듭니다. 이후 인버전이라는 개념을 통해, 인서션 소트의 동작이 왜 데이터마다 다른 시간 복잡도를 갖는지 이해해보았고, 이를 바탕으로 셸 소트라는 알고리즘의 아이디어까지 알아보았습니다.

본문의 자바 코드는 깃허브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): 본문에서 동물 병원 문제로 언급한 같은 문제.

• Java Microbenchmark Harness (JMH): 자바 코드의 소요 시간 측정에 사용한 도구.