[CM301] 04. 정렬(sort)

 이전 주제에서 정렬 문제를 계산 모델의 예시로 들었었고, 회귀의 예시로서 병합정렬도 살펴 보았습니다. 그러니 이번에는 정렬과 그 알고리즘에 대해 좀 더 자세히 다뤄보고자 합니다.

 정렬(sort)문제는 배열의 요소들을 특정한 순서로 재배치하는 것이 목표입니다. 몇몇 알고리즘들은 배열이 모두 정렬되어 있다는 가정이 필요한 경우가 많아서, 정렬된 배열을 만드는 작업은 효율적인 알고리즘을 만드는 데에 상당히 중요한 역할을 하게 됩니다.

 이제부터 몇 가지 대표적인 정렬 알고리즘과 그 복잡도에 대해 다뤄보겠습니다.

작성된 모든 코드는 Python의 형식을 빌린 유사 코드이며, 문법을 다소 무시한 부분이 있기 때문에 실행이 되지 않습니다.

버블정렬 (Bubble sort)

def bubble_sort(x[1, ..., n]):
  for i := 1 to n-1:  # 총 n-1번 반복
    for j := 1 to n-i:  # 반복 마다 n-i번 까지 버블 동작 수행 (오른쪽 끝 i개는 정렬되어 있음)
      if (x[j] > x[j+1]):  # 만약 버블 왼쪽이 오른쪽 보다 크다면
        change x[j], x[j+1]  # 자리를 바꾼다
    
    if x remains as same:  # 만약 반복을 돌았는데도 변화가 없다면 정렬이 이미 끝난 것
      break;

  return x

 버블 정렬은 인접한 두 원소를 비교해 순서를 바꾸면서, 큰 값을 뒤로 ‘떠오르게’하는 방법입니다. 두 번째 루프가 끝날 때 마다 1 ~ n-i번째 수 중 가장 큰 수가 오른쪽 끝으로 이동하기 때문에, 정렬이 가능합니다.

 최악의 경우는 입력값이 내림차순으로 정렬되어 있을 때 입니다. 이 경우 매번 change가 호출되기 때문에, 시간 복잡도는 $O(n^2)$이 됩니다. 추가 메모리를 쓰지 않기에 공간 복잡도는 $O(1)$입니다.

삽입정렬 (Insertion sort)

def insertion_sort(x[1, ..., n]):
  for i := 2 to n:
    m = x[j]  # 삽입할 요소 저장

    j = i - 1
    while j > 0 and x[j] > m:  # m보다 더 작은 값이 나올 때 까지
      x[j+1] = x[j]  # 왼쪽의 값을 오른쪽으로 한 칸 이동
      j -= 1

    x[j+1] = m  # 빈 자리에 삽입
  
  return x

 삽입 정렬은 앞에서부터 원소를 하나씩 꺼내 이미 정렬된 부분에 삽입하는 방법입니다. 새로운 요소를 삽입할 때는 이미 정렬된 부분이 정렬 상태를 유지하도록 올바른 위치를 찾기 때문에, 정렬이 가능합니다.

 최악의 경우는 입력값이 내림차순으로 정렬되어 있을 때 입니다. 이 경우 매번 while문을 j=0까지 돌기 때문에, 시간 복잡도는 $O(n^2)$이 됩니다. 추가 메모리를 쓰지 않기에 공간 복잡도는 $O(1)$입니다.

선택정렬 (Selection sort)

def selection_sort(x[1, ..., n]):
  for i := 1 to n-1:
      min_idx = i
      for j := i+1 to n:  # 정렬되지 않은 구간에서
          if A[j] < A[min_idx]:  # 최솟값의 인덱스 찾기
              min_idx = j

      change A[i], A[min_idx]  # 정렬된 구간 끝에 최솟값을 붙인다

 선택 정렬은 배열 전체의 최솟값을 찾아 첫 번째 위치로 옮기고, 나머지 구간에서 다시 최솟값을 찾아 두 번째 위치로 옮기는 과정을 반복하는 방법입니다. 매번 최솟값을 찾아 추가하기 때문에, 정렬이 가능합니다.

 항상 똑같이 순회를 하기 때문에 특별히 최악의 경우나 최선의 경우가 없습니다. 시간 복잡도는 $O(n^2)$이 되고, 추가 메모리를 쓰지 않기에 공간 복잡도는 $O(1)$입니다.

퀵 정렬 (Quick sort)

def quick_sort(x[1, ..., n], p, r):
  if p < r:
    q = partition(x[1, ..., n], p, r)  # 두 구간으로 나누기
    quick_sort(x[1, ..., n], p, q-1)  # 왼쪽 부분에 대해서 quick sort
    quick_sort(x[1, ..., n], q+1, r)  # 오른쪽 부분에 대해서 quick sort
  
  return x

# p 번째 요소를 기준으로 하여 그 보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분리
def parition(x[1, ..., n], p, q):
  pivot = x[p]  # p번째 요소를 기준으로
  i = p  # 왼쪽 부분의 끝 위치
  for j := p+1 to q:
    if x[j] <= pivot:  # pivot보다 작은 값은
      i += 1  # 왼쪽 부분의 끝으로
      change x[i], x[j]  # 이동
    # pivot보다 큰 값은 오른쪽으로 밀려남
  change x[p], x[i]  # 분리가 끝나면 pivot을 두 구간 사이로 이동

  return i

 퀵 정렬은 하나의 기준점(pivot)을 기준으로 그 보다 작은 값과 큰 값들을 분리한 뒤, 각각에 대해서 다시 재귀 호출을 하는 방법입니다. 퀵정렬은 배열을 두 개의 구간(partition)으로 나누는데, 한 구간의 길이가 1이면 기준점과 그 구간은 완전히 정렬되기 때문에, 재귀가 모두 끝나는 시점에서는 정렬이 가능합니다.

 퀵정렬은 분할 정복을 사용하였습니다. 재귀 호출을 통해 계산을 동시에, 빠르게 하기 위해서요. 배열을 두 개의 하위 배열로 나누었고, 하위 배열의 크기는 기준점(pivot)에 따라 그 길이가 달라집니다. 그리고 parition()함수의 경우 배열 전체를 순회하기 때문에, 걸리는 시간은 $\Theta(n)$으로 둘 수 있습니다. 따라서 회귀식은 다음과 같이 나타낼 수 있습니다.

\[T(n) = T(an) + T(bn) + \Theta(n) \quad (an + bn = n-1)\]

 최선의 경우는 구간이 정확히 반으로 나뉘는 경우입니다. 이렇게 되면 한 쪽으로 치우치는 경우 없이 모든 하위 문제가 고르게 계산되어 계산 시간이 줄어듭니다. 시간 복잡도는 $\Theta(n\log{n})$이 됩니다.

\[T(n) = T(n/2) + T(n/2) + \Theta(n) = 2T(n/2) + \Theta(n) = \Theta(n\log{n})\]

 최악의 경우는 입력값이 내림차순 혹은 오름차순으로 정렬되어 있을 때입니다. 구간을 나누는 단계에서 기준점은 항상 맨 앞의 요소(p 번째)를 사용하는데, 배열이 이미 정렬되어 있으면 구간이 고르게 분할되지 않고 한 구간에만 요소들이 다 몰리기 때문입니다. 이렇게 되면 분할 정복을 사용하는 이유가 사라지죠. 시간 복잡도는 $\Theta(n^2)$이 됩니다.

\[T(n) = T(0) + T(n-1) + \Theta(n) = \Theta(n^2)\]

랜덤 퀵정렬 (Randomized quick sort)

def quick_sort(x[1, ..., n], p, r):
  # 이전과 동일

# 기준점을 무작위로 골라 그 보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분리
def rand_parition(x[1, ..., n], p, q):
  rand_idx = random(p, q)  # p ~ q번째 중 무작위 요소를 선택해
  pivot = x[rand_idx]  # 기준점으로 설정
  change x[rand_idx], rand[p]  # 기준점은 앞으로 보내기
  i = p  # 왼쪽 부분의 끝 위치
  for j := p+1 to q:
    if x[j] <= pivot:  # pivot보다 작은 값은
      i += 1  # 왼쪽 부분의 끝으로
      change x[i], x[j]  # 이동
    # pivot보다 큰 값은 오른쪽으로 밀려남
  change x[p], x[i]  # 분리가 끝나면 pivot을 두 구간 사이로 이동

  return i

 퀵정렬은 대부분 빠른 속도를 보여주지만, 기준점이 무엇으로 잡히냐에 따라 실행시간의 변동이 크다는 단점이 있습니다. 랜덤 퀵정렬은 맨 왼쪽의 요소를 기준점으로 선택하지 않고 무작위로 선택하여 이 문제를 보완했습니다. 이렇게 하면 퀵정렬은 더 이상 입력값의 배열 순서에 영향을 받지 않게 되니까요.

 그렇다면 무작위 선택을 했을 때 복잡도가 어떻게 변하는지 직접 계산해봅시다. 우선 구간들이 어떤 비율로 나뉠지 모르니, k:n-k-1의 비율로 구간이 나뉠 때의 복잡도를 계산하여 평균을 내야 할겁니다. k는 0부터 n-1이 될 수 있으므로 확률은 고르게 $1/n$으로 둘 수 있습니다.

\[E[T(n)] = \sum_{k=0}^{n-1} \frac{1}{n} \; \left\{ E[T(k)] + E[T(n-k-1)] + \Theta(n) \right\} = \frac{2}{n} \; \sum_{k=0}^{n-1} E[T(k)] + \Theta(n)\]

 $k = 0, 1$인 경우는 $\Theta(n)$과 같기 때문에 해당 항에 포함시킬 수 있습니다.

\[E[T(n)] = \frac{2}{n} \; \sum_{k=2}^{n-1} E[T(k)] + \Theta(n)\]

 이제 이 식의 상한선이 무엇인지를 알아야 하는데, 여기서는 대입(substitution)법을 사용해보겠습니다. $k < n$인 경우에 대해 $E[T(k)] \leq ck\log{k}$라고 가정하겠습니다.

\[E[T(n)] \leq \frac{2}{n} \; \sum_{k=2}^{n-1} ck\log{k} + \Theta(n)\]

 이미 알려식 계산식으로 약간의 트릭을 사용하겠습니다.

\[\sum_{k=2}^{n-1}k\log{k} \leq \frac{1}{2}n^2\log{n} - \frac{1}{8}n^2\]

 이 사실을 사용할거에요(그래서 k=0,1 값을 미리 없애 놓은 겁니다).

\[E[T(n)] \leq \frac{2c}{n} \; \sum_{k=2}^{n-1} (\frac{1}{2}n^2\log{n} - \frac{1}{8}n^2) + \Theta(n) = cn\log{n} - \frac{1}{4}cn + \Theta(n)\]

 $E[T(n)] \leq cn\log{n}$을 만족하기 위해서는 $\frac{1}{4}cn - \Theta(n) \geq 0$이 성립하기만 하면 됩니다. 따라서 이 조건을 만족할 수 있을 만큼 충분히 큰 $c$를 잡는다면, $E[T(n)] \leq cnㅊ{n}$임을 보일 수 있고, 따라서

\[E[T(n)] = O(n\log{n}) \quad \Box\]

 입력값의 배열이 어떤 식으로 달라져도 평균적으로 $O(n\log{n})$의 시간만 걸리게 됩니다. 만약 $O(n^2)$인 경우가 나오더라도, 극히 드문 확률일거에요. 여러분의 알고리즘이 극악의 확률을 뚫고 최솟값이나 최댓값만 계속 기준점으로 선택한다면요.

힙 정렬 (Heap sort)

def heap_sort(x[1, ..., n]):
  # 1 단계 : 힙이 아닌 리스트를 힙 구조로 만들기
  for k := n/2 to 1:  # 계산량을 줄이기 위해 잎 노드는 건너뜀
    sink(k);  # 밑에서부터 힙 복구

  # 2 단계 : 맨 앞의 최댓값을 하나 씩 빼내기
  while (n > 1):  # 힙을 모두 순회할 때까지
    exch(1, n);  # 맨 앞의 노드를 리스트 맨 뒤로 옮기고 맨 뒤에 있던 노드를 맨 앞으로 이동
    n -= 1  # 힙 크기 한 칸 감소
    sink(1);  # 맨 앞 노드를 빼내 깨져버린 힙을 다시 복구

 힙 정렬은 요소들이 계층에 따라 대소관계를 가지는 데이터 구조인 힙(Heap)을 사용하여 수행하는 정렬 방법입니다. 힙의 구조상 제일 앞에 오는 요소가 최댓값을 가지게 되는데, 이 점을 활용해 1. 최댓값을 빼내 리스트 제일 뒤에 둔다. 2. 최댓값이 빠진 데이터 구조를 다시 힙으로 만든다. 이 두 과정을 반복하여 리스트를 오름차순으로 정렬할 수 있게 됩니다.

 힙 정렬에서 보아야하는 연산은 역시 sink()입니다. 여기서 자세히 설명하지는 않겠지만, sink는 일반적으로 힙을 이진 트리로 구성했을 때 그 트리의 높이, 즉 $\log{n}$만큼의 연산을 수행하게 됩니다. 그리고 이 sink가 while문을 통해 리스트의 크기 n만큼 순회하게 되므로, 실행시간은 $O(n\log{n})$이 됩니다.

위 코드를 보아도 바로 이해가 되지 않을 겁니다. 힙정렬을 설명하기 위해서는 데이터 구조인 힙과 힙 구성을 위해 필요한 함수들(sink, exch)에 대해 알아야 하는데, 그 설명이 빠져 있거든요. 여기서는 힙정렬의 존재에 대해서만 짚고 넘어가고, 힙에 대한 더 자세한 내용은 ‘데이터 구조’에서 다루도록 하겠습니다.

 이전 장에서 다룬 병합정렬까지 포함하여 최선과 최악의 경우 시간 복잡도를 정리해보겠습니다. 여기서 안정성이란, 리스트에 똑같은 요소가 존재할 때 정렬 후에도 두 요소의 순서가 유지되는 성질을 말합니다. 예를 들어 5개 길이의 리스트에서 첫 번째와 세 번째 요소가 같은 값을 가질 때, 정렬이 끝난 후에도 첫 번째에 있던 요소가 세 번째에 있던 요소 보다 앞에 있게 된다면 그 정렬은 안정성이 있다고 말할 수 있습니다.

알고리즘	최선	평균	최악	추가 공간 사용	안정성
버블정렬	$O(n)$	$O(n^2)$	$O(n^2)$	X	안정
삽입정렬	$O(n)$	$O(n^2)$	$O(n^2)$	X	안정
선택정렬	$O(n^2)$	$O(n^2)$	$O(n^2)$	X	불안정
퀵정렬	$O(n\log{n})$	$O(n\log{n})$	$O(n^2)$	X	불안정
랜덤 퀵정렬	$O(n\log{n})$	$O(n\log{n})$	$O(n^2)$	X	불안정
힙정렬	$O(n\log{n})$	$O(n\log{n})$	$O(n\log{n})$	X	불안정
병합정렬	$O(n\log{n})$	$O(n\log{n})$	$O(n\log{n})$	O	안정

하한을 돌파하는 정렬들

 이때까지 여러가지 정렬 알고리즘에 대해 살펴보았는데, 볼 수 있듯이 모든 알고리즘은 평균 실행시간이 $O(n\log{n})$을 넘지 않습니다. 앞서 2장에서 문제의 복잡도에 대해 다루었던 것을 기억하나요? 모든 문제는 시간 복잡도의 하한선(Lower bound)이 존재하고, 정렬 문제의 경우 그 하한선이 $O(n\log{n})$이라는 것을 보였습니다. 그런데 이것은 의사 결정 트리를 계산 모델로 했을 때를 가정한 결과였습니다. 의사 결정 트리는 어떤 두 요소 a와 b가 있을 때 두 요소의 대소를 비교한 후 그 결과에 따라 순서를 배치하는 연산 방식이었습니다.

 그렇다면, 의사 결정 트리가 아닌 다른 계산 모델을 사용한다면 $O(n\log{n})$보다 더 빠른 알고리즘을 찾을 수 있지 않을까요? 실제로 의사 결정 트리를 사용하지 않으면서, 이보다 (어쩌면)더 빠른 알고리즘이 존재합니다.

계수 정렬 (Counting sort)

def counting_sort(x[1, ..., n]):
  M = max(x)  # 최댓값 (정수여야 할 것)
  count = [0 for i := 0 to M]  # 등장 횟수를 기록할 리스트
  res = [0 for i := 1 to n]  # 재정렬할 리스트
  
  for i := 1 to n:  # 모든 x의 요소에 대해
    count[x[i]] += 1  # 해당 값의 개수 갱신
  
  for i := 1 to M:  # 각 숫자별로
    count[i] += count[i-1]  # count의 누적합 계산
  
  for i := 1 to n:  # 모든 x의 요소에 대해
    res[count[x[i]]] = x[i]  # 누적합에 해당하는 자리에 삽입
    count[x[i]] -= 1  # 누적합은 1 감소
  
  return res

 계수 정렬은 리스트의 모든 값이 정수일 때, 그 값의 등장 횟수를 이용해 위치를 결정하는 정렬 방법입니다. 등장했던 숫자들을 인덱스로 하여 재배열하는 것이기 때문에 오름차순으로 정렬이 가능해집니다.

 천천히 풀어서 설명해보겠습니다. [1, 2, 1, 3, 2, 1]이라는 배열을 정렬한다고 해봅시다. 우선 주어진 배열의 최댓값(여기서는 3)을 구하고, 0 ~ 3의 인덱스를 가지는 count 리스트를 만들어 각 숫자별 등장 횟수를 기록합니다. 그리고 각 요소 별로 누적합을 계산합니다. 이 값은 요소별로 재정렬되어야 할 위치를 표시할 것입니다.

 이제 주어진 리스트를 순회할텐데, 각 요소의 값으로 count에 인덱스 접근을 하여 재정렬 위치를 참조할 것입니다. 가령 첫 번째 수인 1의 경우 count[1] = 3 이므로, 정렬된 리스트에서는 세 번째 자리에 1이 위치할 것입니다. 이후 또 다른 1이 등장할 수 있는데(1이 3개 있다고 기록되어 있으니까요), 자리가 겹치는 것을 막기 위해 이 count[1]의 값을 1 감소 시켜줘야 합니다.

 이걸 계속 반복하면, 정렬이 완료됩니다.

 이 알고리즘의 시간 복잡도는 어떨까요? 일단 보기에는 한 층의 반복문만 보이기에, $O(n)$으로 생각할 수 있습니다. 하지만 반복문 중 일부는 입력값의 크기 n이 아닌 입력값 중 최댓값인 M만큼 반복하기 때문에, 엄밀히 따지자면 $O(n+M)$의 시간 복잡도를 가진다고 보아야 합니다.

 선형 시간의 복잡도입니다! $O(n\log{n})$보다 더 짧은 시간을 가지네요. 하지만 아쉽게도, 계수 정렬은 입력값이 모두 정수여야만 가능하다는 문제가 있습니다. 거기가 추가 공간(count 리스트)이 필요한데, 이는 입력값의 최댓값에 따라 달라진다는 문제도 있죠. 만약 입력값이 [1, 2, 100]로 들어온다면, 단 세 개의 수 밖에 가지고 있는데도 count는 최댓값인 100의 길이를 가져야 합니다.

기수 정렬 (Radix sort)

def radix_sort(x[1, ..., n]):
  bucket = [Queue([]) for i := 0 to 9]  # 큐 리스트
  M = len(str(max(x)))  # 가장 큰 자리수

  for i := 1 to M:  # 각 자리수 마다
    for j := 1 to n:  # 모든 요소에 대해
      d = x[j] / 10 ** (i-1) % 10  # 자리 숫자 계산
      bucket[d].enqueue(x[j])  # 해당 큐에 추가
    
    idx = 0  # x 인덱스
    for j := 0 to 9:  # 모든 큐에 대해
      while bucket[j]:  # 큐가 다 빌 때까지
        x[idx] = bucket[j].dequeue()  # 꺼내서 x에 삽입
        idx += 1  # 인덱스 1 만큼 증가
  
  return x

 기수 정렬은 자리수 별로 숫자를 정렬하는 정렬 방법입니다. 일의 자리를 기준으로 정렬, 그 다음에는 십의 자리를 기준으로 정렬하는 방식이죠. 각 자리마다의 정렬은 계수 정렬과 유사하게 각 숫자에 해당하는 인덱스 접근을 수행합니다. 만약 중복되는 값이 있다면, 큐(Queue)를 만들어 저장합니다.

 또 다른 예를 들어보겠습니다. 이번엔 [32, 14, 15, 423, 24]를 정렬해야 한다고 해봅시다. 우선 인덱스 접근을 위해 0 부터 9까지의 큐를 가지는 배열을 준비해둡니다. 그리고 배열을 순회하며 일의 자리 숫자에 해당하는 큐에 값을 저장합니다.

 이제 0번 큐 부터 9번 큐 까지 순회하며 요소들을 꺼내 재배치합니다. 이렇게 하면 적어도 일의 자리를 기준으로는 정렬이 완료됩니다.

 이걸 계속 반복하면, 정렬이 완료됩니다. 이미 이전 자리를 기준으로 정렬이 완료 되어 있고, 큐는 선입 선출 원칙을 지키기 때문에 이전 자리의 정렬 결과를 그대로 보존할 수 있습니다.

 이 알고리즘의 시간 복잡도는 어떨까요? 코드에는 이중으로 중첩된 반복문이 존재합니다. 모든 자릿수에 대해 연산을 수행하면서 x를 순회하기 때문입니다. 따라서 시간 복잡도는 $O(Mn)$입니다. 이 알고리즘 또한 $O(n)$의 선형 알고리즘으로 볼 수 있지만, 계수 정렬과 같은 문제점을 공유합니다. 자릿수를 이용해 정렬한다는 점에서 똑같이 정수만을 받는다는 조건이 필요하고, 최대 자리수 M에 영향을 받게 된다는 것이죠.

 계수 정렬과 기수 정렬 모두 앞서 소개했던 정렬들보다 훨씬 좋은 성능을 보입니다. 비록 정수라는 제한적 조건이 필요하지만, 정수 숫자를 다루는 경우 자체가 드물지 않기 때문에 적당한 영역이라면 높은 효율을 낼 수 있는 알고리즘들입니다.