브리지 게임

삽입 정렬에 대해 여러 책이 브리지 게임 이야기를 한다.

이미 정렬된 카드 사이에 새 카드를 꽂아 넣어서, 다른 카드가 밀려나는 모습을 생각해보면 이해하기 쉽다.

TAOCP에서는 다음과 같이 언급한다.

A. 삽입 정렬(insertion sort). 항목을 한 번에 하나씩 살펴보면서, 각각의 새 항목을 그 때까지 정렬된 항목들에 상대적인 적절한 위치에 삽입한다. (이는 수많은 브릿지 플레이어들이 자신의 손패를 카드 한 장씩 뽑아서 정렬할 때 사용하는 방법이다.) 1

이 알고리즘을 구현할 때에는 아이템을 삽입할 공간을 만들기 위해, 아이템보다 큰 항목을 전부 오른쪽으로 이동시켜야 한다.

그러면 빈 공간이 발생하게 되고, 빈 공간에 아이템을 삽입하면 된다.

특징

삽입 정렬의 실행 시간은 초기 입력 배열에서 항목들이 정렬된 상태에 의존적이다. 예를 들어 배열이 매우 크고 항목들이 이미 정렬된(또는 거의 정렬된) 상태라면 무작위 순서 또는 역순의 입력 배열에 비해 훨씬 더 빠르게 정렬을 완료한다.2

삽입 정렬은 완전히 무작위적이지 않고 부분적으로 순서가 맞는 특정한 형태의 배열에 대해서 그 크기가 대단히 크더라도 잘 동작한다. 실제 상황에서는 그러한 데이터를 상대로 해야 할 경우가 자주 있다. 예를 들어 앞서 언급되었듯이, 이미 정렬이 완료된 배열을 상대로 삽입 정렬을 적용하면 무슨 일이 일어나는지 생각해보자. 각 항목들은 검사될 때마다 최종적인 위치로 확정되고 이에 따라 전체 실행 시간이 선형이 된다([[/algorithm/selection-sort]]{선택 정렬}은 이런 상황에서 제곱 시간이 걸린다). 모든 키가 서로 같은 경우에도 동일하다.2

  • 삽입정렬은 부분적으로 정렬되었거나 이미 정렬된 상태일 때 최적인 알고리즘이다.
  • 삽입 정렬은 크기가 작은 배열에 대해서도 효과적이다.
  • 삽입 정렬은 중요하다. 고급 정렬 알고리즘의 중간 단계에서도 자주 나타나기 때문.

복잡도

명제 B. 삽입 정렬은 중복 없는 키를 가진 무작위로 정렬된 크기 \(N\)의 배열에 대해 평균적으로 \(\sim { N^2 \over 4 }\) 번의 비교와 \(\sim { N^2 \over 4 }\) 번의 교환을 수행한다. 최악 조건에서는 \(\sim { N^2 \over 2 }\) 번의 비교와 \(\sim { N^2 \over 2 }\) 번의 교환을 수행하고 최적 조건에서는 \(N-1\) 번의 비교와 \(0\) 번의 교환을 수행한다.2

  • 최악의 경우 \(O(N^2)\)
  • 평균적인 경우 \(O(N^2)\)
  • 최선의 경우 \(O(N)\)
    • 최선의 경우는 이미 정렬이 완료된 상태이다.
    • 중복된 아이템이 없다면 최선의 경우일 확률은 \({ 1 \over N! }\).

최고-상황에서는 n개의 항목이 모두 제 위치에 있고, 따라서 삽입 정렬은 선형 시간 \(O(n)\)을 따른다. (이미 정렬된 원소를 정렬할 일은 자주 있지 않으므로) 이런 특성은 사소한 것처럼 보이지만, (이 장에서 논의하는) 비교에 기반을 둔 정렬 알고리즘 중에서 삽입 정렬만 이러한 동작 특성을 보이므로 눈여겨볼 만하다. 3

중복 아이템이 있다면 교환 횟수가 줄어들게 되므로 삽입 정렬의 효율은 상승한다.

문제점

랜덤 데이터에 대해 보수적.

\(n\)개의 모든 항목이 서로 다르고 배열이 '무작위'라면(자료의 모든 순열이 같은 비율로 일어난다면), 각 항목은 최종 위치에서 평균적으로 \(\frac{n}{3}\)의 거리 안에서 이동하기 시작한다. 그러므로 평균-상황과 최저-상황에서 n 개의 항목은 선형 개수의 위치만큼 이동해야 하고, 삽입 정렬은 2차 시간, 즉 \(O(n^2)\)을 따른다. 3

국소 치환 정렬.

삽입 정렬의 문제는 각 원소가 한 번에 한 칸씩만 움직이는 (국소 치환 정렬(local transposition sort)이라고 부르는) 보수적인 알고리즘 부류라는 점이다. 3

구현 예제

public class InsertionSort {

  public static void sort(int[] a) {
    final int size = a.length;

    for (int i = 1; i < size; i++) {
      for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
        final int temp = a[j];
        a[j] = a[j-1];
        a[j-1] = temp;
      }
    }
  }
}

function sort(a) {
  size = a.length
  for(i = 1; i < size; i++) {
    insert(a, i, a[i])
  }
}

function insert(a, pos, value) {
  j = pos - 1
  while(j >= 0 && a[j] > value) {
    a[j + 1] = a[j]
    j--
  }
  a[j + 1] = value
}

함께 읽기

  • [[/algorithm/average-complexity]]{평균 계산 복잡도 구하기}
  • [[/algorithm/shell-sort]]{셸 정렬}

참고문헌

  • The Art of Computer Programming 3 정렬과 검색(개정2판) / 도널드 커누스 저 / 한빛미디어 / 초판 2쇄 2013년 02월 10일
  • 사전처럼 바로 찾아 쓰는 알고리즘 / 조지 T. 하인만, 게리 폴리케, 스탠리 셀코 공저 / 전경원 역 / 한빛미디어 / 초판 2쇄 2011년 10월 20일 / 원제: Algorithms In A Nutshell
  • 알고리즘 [개정4판] / 로버트 세지윅, 케빈 웨인 저/권오인 역 / 길벗 / 초판발행 2018년 12월 26일

주석

  1. TAOCP 3권. 5.2장. 101쪽. ↩

  2. 알고리즘 [개정4판]. 2장. 249쪽. ↩ ↩2 ↩3

  3. 사전처럼 바로 찾아 쓰는 알고리즘. 92쪽. ↩ ↩2 ↩3