Sort an Array

정수 배열을 정렬하자. 배열의 길이는 최대 \(5 \times 10^4\)이고 값은 32비트 정수 안에 다 담긴다.

Merge Sort

병합 정렬을 구현해보았다.

먼저 merge_sort에서는 계속 배열을 절반씩 나누면서 할 일을 쪼갠다. 그 후 이 배열을 merge 함수 호출을 통해 합친다. 따라서 merge_sort의 베이스 케이스는 배열이 비거나 원소가 1개만 있는 경우이다.

merge 함수가 핵심이다. 여기서는 두 배열 left와 right를 합치는데, 핵심은 합치고 나서 남은 것 원소들은 서로 비교할 필요 없이 곧바로 추가하면 된다는 것이다. 이때, 두 배열을 비교하며 합치는 과정을 인덱스를 기준으로 반복문을 돌았다면, 반복문을 빠져나온 시점에서 두 배열을 순회하던 인덱스를 기준으로 남은 원소를 합쳐야 한다. 파이썬에서는 extend 함수와 슬라이스 연산을 통해서 이를 읽기 쉽고 오류 나지 않게 구현할 수 있다.

def sortArray(nums):
    def merge_sort(arr):
        if len(arr) <= 1:
            return arr
        mid = len(arr) // 2
        left = merge_sort(arr[:mid])
        right = merge_sort(arr[mid:])
        return merge(left, right)

    def merge(left, right):
        result = []
        i, j = 0, 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result.extend(left[i:])
        result.extend(right[j:])
        return result
    return merge_sort(arr)

잡설

병합 정렬은 그 유명한 폰 노이만님께서 1945년에 발명한 알고리즘이다.

병합 정렬의 시간 복잡도가 O(nlogn)인 것은 유명하지만, 이게 왜 이렇게 되는지는 생각보다 직관적이지 않다. 이거는 알고리즘 복잡도 분석에 쓰이는 마스터 정리를 이용해야 하는데, 코드를 보면 다음 재귀적인 점화식이 성립함을 알 수 있다: \(T(n) = 2T(n/2) + n\), 여기서 \(T(n)\)은 길이 n의 배열을 병합 정렬하는데 걸리는 복잡도이다. 즉, 이 점화식은 길이 n의 배열을 병합 정렬할 때 이를 크기가 n/2인 부분 문제 2개로 나눠서 수행한다는 것을 뜻한다. 따라서 마스터 정리에 따라 \(a = 2, b=2, f(n) = n\) 이고 \(c = log_{2}{2} = 1\) 이므로 \(f(n) = \Theta(n^{c} log^{k}n)\) (\(c = 1, k = 0\)) 가 된다. 따라서 \(T(n) = \Theta(n^{log_{b}a} log^{k+1} n) = \Theta(n^1 log^1 n) = \Theta(nlogn)\)이 된다.

위의 구현에서의 공간 복잡도는 O(n)인데, 다양한 변형에서 제자리 병합 정렬을 구현하기도 했지만 이해하기 어려워서 여기서는 구현하지 않았다.

병합 정렬은 원소끼리 직접 비교 연산을 하는 비교 정렬인데, 그 중에서도 같은 값을 가진 원소의 원래 순서가 유지되는 안정 정렬(stable sort)에 속한다.

병합 정렬은 배열 뿐만 아니라 링크드 리스트의 정렬에도 탁월해서, 많은 함수형 언어의 기본 정렬로 채택되어 있다.

파이썬의 기본 정렬인 팀 소트는 병합 정렬과 삽입 정렬의 하이브리드 정렬이다.

힙 정렬

힙 정렬은 데이터 구조인 힙, 그 중에서도 최대 힙을 이용한 정렬이다. 방법은 이렇다.

배열을 최대 힙으로 만든다.
첫 번째 원소(최대값)를 배열의 제일 마지막 원소와 바꾸고, 배열의 크기를 하나 줄인다.
siftdown() 함수를 호출해서 첫 번째 원소를 적절히 걸러서 다시 최대 힙으로 만든다.
원소가 하나 남을 때 까지 2번으로 돌아가서 반복한다.

이때 3번의 siftdown()이 O(logn)의 복잡도가 소요되고 이를 n번 반복하므로 총 복잡도는 O(nlogn)이 된다. 참고로 1번인 힙을 만드는 작업은, siftup()으로 힙을 만들면 O(nlogn)의 복잡도를 갖고 siftdown()으로 만들면 O(n)의 복잡도를 가지므로, 항상 siftdown()을 구현해야 한다는 것만 외워두자. 이거 복잡도가 왜 O(n)인지 증명하는 것은 꽤 어렵기 때문에 일단은 넘어간다.

아무튼, 힙은 배열을 이용해서 완전 이진 트리(complete binary tree)를 구축하여 만드는데, 이때 배열의 인덱스로부터 곧바로 완전 이진 트리에서의 왼쪽과 오른쪽 자식의 인덱스를 계산할 수 있기 때문이다.

siftdown() 연산은 다음과 같다. idx에 있는 원소를 두 자식과 비교하면서 힙 성질을 만족하도록 계속 재귀적으로 스왑한다. 반복문으로 구현해도 되지만 재귀 함수로 구현하는 것이 이해하기도 좋고, 완전 이진 트리라는 것이 불변식으로 보장되므로 재귀의 깊이도 logn임이 보장되어 괜찮다. 이 연산은 힙 데이터 구조에서 원소의 삭제에 해당한다. 힙 꼭대기에 있는 원소를 삭제하고 나면, 힙의 제일 마지막에 있는 원소를 힙의 루트에 위치시킨 다음 시프트 다운하여 힙 성질을 유지하도록 한다.

def siftdown(heap, size, idx):
    left, right = 2*idx + 1, 2*idx + 2
    largest = idx
    if left < size and heap[largest] < heap[left]:
        largest = left
    if right < size and heap[largest] < heap[right]:
        largest = right
    if largest != idx:
        heap[largest], heap[idx] = heap[idx], heap[largest]
        siftdown(heap, size, largest)

siftup() 연산은 이 연산의 정확히 듀얼이다. idx에 있는 원소에서 출발해서, 부모와 비교하면서 힙 성질을 만족하도록 타고 올라가는 연산이다. 실제로 이 연산은 힙 데이터 구조에서 원소의 삽입에 해당한다. 힙의 제일 마지막에 원소를 추가한다음, 사이즈를 늘려서 시프트 업하여 힙 성질을 유지하도록 한다. 하지만, 힙 데이터 구조를 구현할 게 아니라 그냥 힙 정렬만 필요하다면 굳이 구현하지 않아도 된다.

def siftup(heap, idx):
    if idx == 0:
        return
    parent = (idx - 1) // 2
    if heap[parent] < heap[idx]:
        heap[parent], heap[idx] = heap[idx], heap[parent]
        siftup(heap, parent)

아무튼 여기서는 힙 정렬만이 필요하니, 시프트 다운 연산만을 이용해서 힙 정렬을 구현해보자. 먼저 배열을 힙으로 만드는 연산인 heapify가 필요한데, 시프트 다운 연산을 이용하면 다음과 같이 구현할 수 있다.

def heapify(arr):
    size = len(arr)
    for i in reversed(range(size//2))
        siftdown(arr, size, i)

전체 크기가 아니라 size / 2부터 시작할 수 있는 이유는 바로 다음 두 가지 성질 때문이다.

힙은 완전 이진 트리이므로 인덱스로부터 부모 인덱스를 쉽게 계산할 수 있다. 0-indexed인 경우 (idx - 1) // 2, 1-indexed인 경우 idx // 2가 바로 부모 노드의 인덱스이다.
시프트 다운 연산은 가장 마지막 리프 노드의 부모 노드로부터 시작하면 된다. 즉 배열의 절반은 스킵하고 시작할 수 있다. 그리고 이 성질이 시프트 다운으로 힙을 구축하는 복잡도가 시프트 업으로 구축하는 복잡도보다 더 작은 데에도 영향을 준다.

참고로 시프트 업 연산을 이용한 힙 구축은 다음과 같다.

def heapfiy_up(arr):
    for i in range(len(arr)):
        siftup(arr, i)

최종적으로 이를 합친 힙 정렬은 다음과 같다.

def sortArray(nums):
    arr = nums[:]
    heapify(arr)
    for i in reversed(len(arr)):
        arr[i], arr[0] = arr[0], arr[i]
        siftdown(arr, i, 0)

reversed(len(arr))을 순회하기 때문에, 첫 번째 원소와 마지막 원소를 스왑하고 나서 사이즈를 하나 줄인 값이 곧 현재 순회중인 인덱스가 된다.

잡설

힙 정렬도 병합 정렬과 마찬가지로 비교 연산을 수행하는 비교 정렬인데, 병합 정렬과 다르게 같은 원소의 원래 위치가 보장되지 않는다. 즉, 안정 정렬이 아니다. 힙을 만드는 과정과 힙 성질을 유지하는 과정에서 같은 원소끼리의 상대적 순서를 잃기 때문이다.

힙 정렬은 부가적인 데이터 구조가 필요없기 때문에 O(1)의 공간 복잡도를 갖는다. 다만, 완전 이진 트리를 배열에 맵핑하는 성질을 활용해야 하므로, 리스트와 같은 데이터 구조는 정렬할 수 없다.

힙 정렬의 이론적인 복잡도는 O(nlogn)이지만 실제 구현 벤치마크에서는 퀵 정렬보다 느린데, 그 이유는 배열 크기가 커질수록 힙 성질을 유지하기 위한 연산의 지역성이 떨어져서 캐시 친화도가 떨어지기 때문이다. 그래서, 잘 구현된 퀵 정렬은 일반적인 힙 정렬보다 2~3배 쯤 더 빠르다는 연구 결과도 있다. 그래서 구현하기 쉬운 정렬은 힙 정렬이지만, 하드웨어의 성질을 이용해서 평균적으로 더 빠른 정렬은 퀵 정렬이다.

힙 성질을 유지하기 위한 두 함수 이름 시프트 다운과 시프트 업은 위키피디아 기준인데, 실제로 파이썬의 힙 구현에는 이름이 반대로 되어 있다. 즉, 파이썬의 시프트 다운은 위키피디아에서의 시프트 업이고, 파이썬의 시프트 업은 위키피디아에서의 시프트 다운이다. 용어가 이렇게 꼬인 이유는 바이너리 힙 문서의 참조에서 찾을 수 있었다. 일단 힙 정렬은 힙 데이터 구조와 함께 1964년에 J.W.J. 윌리암스에 의해 발명되었고, 이후 같은 해에 플로이드에 의해서 제자리 정렬 방법과 함께 개선된 버전이 연구되었다. 이때 시프트 업과 시프트 다운 이름이 제안된 것 같은데, 플로이드가 처음 제안한 “시프트 업”은 지금의 “시프트 다운”이고 “시프트 다운”은 지금의 “시프트 업”이다. 즉, 파이썬은 플로이드의 네이밍을 존경(?)해서 이렇게 한 것 같다. 아마 업/다운 기준을 어디에 두느냐에 따라서 네이밍이 달라진 것 같은데, 플로이드의 원래 네이밍에서는 스왑 연산을 기준으로, 즉 “시프트 업”의 경우 힙 성질을 유지하기 위해서 노드의 두 자식 노드 중 어떤 것을 올려야 하는지를 기준으로 네이밍한 것으로 추측하고, 현재의 네이밍은 트리를 탐색하는 방향을 기준으로, 즉 “시프트 다운”의 경우 힙 성질을 유지하기 위해서 어떤 노드에서 출발해서 리프 노드에 도달할 때 까지 모든 자식 노드를 살펴보는 것을 기준으로 네이밍한 것으로 추측한다.

퀵 정렬

마지막으로 퀵 정렬을 구현해보았다. 퀵 정렬은 먼저 피벗이라고 불리는 어떤 원소 하나를 기준으로 삼고, 이 원소를 기준으로 남은 범위를 쪼갠다(partition). 이때 이 쪼개는 연산은, 피벗 원소를 기준으로 피벗보다 작은 모든 원소는 왼쪽에, 피벗보다 큰 모든 원소는 오른쪽에 위치하도록 한 다음, 피벗은 자기 위치를 찾아 들어간다. 그 후 피벗의 위치를 기준으로 나눠진 두 부분 범위에 대해서 또 퀵 정렬을 재귀적으로 수행한다. 따라서, 퀵 정렬이 끝나는 기저 조건은 범위가 0일 때, 즉 모든 정렬이 완료되었을 때이다.

먼저 퀵 정렬 코드는 다음과 같다.

def quicksort(arr, low, high):
    if low >= high:
        return
    pivot = partition(arr, low, high)
    quicksort(arr, low, pivot)
    quicksort(arr, pivot + 1, high)

트리거는 quicksort(arr, 0, len(arr) - 1)과 같이 호출된다. low, high 모두 인덱스이다. 범위가 0인 경우 곧바로 리턴하고, 그렇지 않은 경우는 먼저 파티션 연산을 통해 피벗을 고른 다음, 이 피벗을 기준으로 [low, pivot]과 [pivot+1, high] 두 부분 범위를 또 퀵 정렬해서 타고 들어가면 된다.

파티션 함수는 다음과 같다.

def partition(arr, low, high):
    pval = arr[low]
    while low < high:
        while low < high and arr[high] >= pval:
            high -= 1
        arr[low] = arr[high]
        while low < high and arr[low] < pval:
            low += 1
        arr[high] = arr[low]
    arr[low] = pval
    return low

먼저 low를 피벗 원소로 선택한다. 그 후, [low, high] 범위를 투 포인터로 탐색해가면서, high에서 출발해서 피벗보다 작은 원소는 low 쪽으로, low에서 출발해서 피벗보다 크거나 같은 원소는 high 쪽으로 스왑해 나아간다. 이러고나면 최종적으로 low = high인 시점에서 피벗 기준 정렬이 끝나고, 그 끝난 위치(low 또는 high)가 바로 피벗 원소가 들어갈 자리이므로 거기에 피벗을 넣어준다. 그리고 피벗 위치를 리턴한다.

여기까지 하면 퀵 정렬의 아주 기초적이고 구현하기 쉬운 버전 중 하나를 완성한 것이다. 그런데 실제로 제출하면 타임아웃이 뜬다. 이는 피벗을 항상 low로 잡기 때문인데, 퀵 정렬은 이 피벗을 어떤 값으로 잡느냐에 따라서 시간 복잡도가 꽤나 출렁인다. 그래서 이 피벗을 잘 잡기 위한 수많은 변종 알고리즘들이 있다.

여기서는 일단 타임아웃을 통과하기 위한 목적으로, 피벗을 랜덤하게 선택하도록 구현한다. 말은 쉬운데, 피벗을 랜덤하게 선택하도록 어떻게 구현하면 될까? partition 함수에서 low를 피벗으로 잡고 있으니, 이 부분을 수정하면 될까? partition에서 피벗을 랜덤하게 잡도록 구현하면 생각보다 구현이 까다로워 진다. 그래서 보통은, partition에 진입하기 전에, 먼저 피벗 원소를 하나 랜덤하게 선택한 다음, 이 원소를 low와 스왑해서, partition은 그대로 수정하지 않고 피벗을 랜덤하게 선택한 효과를 얻도록 구현한다. 따라서, 다음과 같이 quicksort 함수만 수정해주면 된다.

import random
def quicksort(arr, low, high):
    if low >= high:
        return
    pi = random.randrange(low, high+1)
    arr[pi], arr[low] = arr[low], arr[pi]
    pivot = partition(arr, low, high)
    quicksort(arr, low, pivot)
    quicksort(arr, pivot+1, high)

혹은, 아래와 같이 그냥 [low, high] 범위의 중앙값을 피벗으로 삼도록 해도 된다.

    ...
    pi = low + (high - low) // 2
    ...

뭘 하든 쌩으로 low를 피벗으로 잡는 것보다는 훨씬 좋은 효율을 보여주고, 둘 다 타임아웃 없이 통과한다.

잡설

퀵 정렬은 그 유명한 토니 호어 님께서 1959년에 발명하고 1961년에 공개된 알고리즘이다. 호어 로직의 그 분 맞다. 호어가 모스크바 대학에서 교환 학생으로 갔을 때, 러시아어와 영어 단어 사이의 번역을 위해서 문자열을 정렬할 필요가 있었는데, 이때 가장 먼저 발명한 정렬이 바로 삽입 정렬이고, 그 이후에 퀵 정렬을 개발했다고 한다.

힙 정렬의 잡설 란에서 설명했듯, 퀵 정렬은 지역성을 아주 잘 활용하는 덕분에, (아주 잘 구현된 경우) 힙 정렬보다는 최대 2~3배 더 빠르고 일반적으로 병합 정렬보다도 빠르다고 한다.

아주 잘 알려진 퀵 정렬의 성질이 있다.

퀵 정렬은 최악의 경우 \(O(n^2)\)의 복잡도를, 평균적으로는 \(\Theta(nlogn)\)의 복잡도를 갖는다. 특히 이미 정렬되어 있거나 부분적으로 정렬된 배열에 대해서는 복잡도가 좋지 못하다.
퀵 정렬은 피벗을 아주 잘 잡아야 한다. 쉽게 구현하려면 첫 번째 or 마지막 or 중간 원소를 잡아버리지만 이러면 별로 소용이 없고, 운에 기댄다면 랜덤한 원소를 피벗으로 잡는 방법이 있다. 피벗을 잘 잡기 위한 연구가 따로 있을 정도로 피벗이 퀵 정렬의 복잡도에 주는 영향은 지대하다.