[CM301] 04. 정렬(Sorting)

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

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

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

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

버블정렬 (Bubble sorting)

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 sorting)

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 sorting)

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 sorting)

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 sorting)

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 sorting)

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)에 대해 알아야 하는데, 그 설명이 빠져 있거든요. 여기서는 힙정렬의 존재에 대해서만 짚고 넘어가고, 힙에 대한 더 자세한 내용은 ‘데이터 구조’에서 다루도록 하겠습니다.

 마지막으로 이전 장에서 다룬 병합정렬까지 포함하여 최선과 최악의 경우 시간 복잡도를 정리하였습니다.

알고리즘	최선	평균	최악	추가 공간 사용	안정성
버블정렬	$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(nlogn)$	$O(nlogn)$	$O(n^2)$	X	불안정
랜덤 퀵정렬	$O(nlogn)$	$O(nlogn)$	$O(n^2)$	X	불안정
힙정렬	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	X	불안정
병합정렬	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	O	안정