정렬 구현 - 삽입·병합·퀵·힙 정렬

이 장에서 배우는 것

앞 장에서 해시 테이블을 만들며 키가 들어갈 위치를 계산했다. 이번에는 값의 크기를 비교하면서 배열 안의 순서를 바꾼다. 같은 정렬 결과를 얻더라도 어떤 값끼리 몇 번 비교하는지, 같은 값을 가진 항목의 순서가 유지되는지는 구현에 따라 달라진다. 정렬은 결과만 보고 내부 동작까지 판단하기 어려운 작업이다.

이 장에서는 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬을 직접 만든다. 네 구현에 같은 입력을 주고, 원소의 키를 비교한 횟수를 표로 출력한다. 코드는 값을 담는 고정 크기 리스트를 배열로 사용한다. 정렬을 만드는 부분에서는 리스트의 크기를 바꾸거나 내장 정렬 기능을 호출하지 않는다.

• 정렬의 안정성이 무엇이며 어떤 조건에서 유지되는지 설명한다.
• 네 정렬이 원소를 이동시키는 과정을 배열 인덱스로 구현한다.
• 키 비교 횟수를 세어 입력 순서와 최악의 경우가 만드는 차이를 확인한다.
• 직접 만든 구현과 내장 정렬의 결과 및 키 비교 횟수를 비교한다.

문제 상황

구현 과제에서 제출 기록을 점수순으로 정렬한다고 하자. 기록에는 점수와 접수 순서가 들어 있다. 점수가 같으면 먼저 접수한 기록이 앞에 있어야 한다. 점수만 올바르게 정렬했다고 과제를 마칠 수는 없다. 동점 기록의 상대적인 순서도 확인해야 한다.

또 다른 조건은 성능 설명이다. “빠르게 실행됐다”는 설명만으로는 입력이 커졌을 때의 동작을 알기 어렵다. 이미 정렬된 입력과 거꾸로 정렬된 입력에서 같은 코드가 서로 다른 수의 비교를 할 수 있다. 이번 실험에서는 실행 시간을 재는 대신, 두 기록의 점수를 비교하는 순간마다 계수를 하나씩 늘린다.

계수는 어떤 일이 몇 번 일어났는지 기록하는 정수다. 여기서는 키 비교 한 번을 관찰 단위로 삼는다. 전공 수업에서는 입력 크기에 따른 비용을 따지는 일을 알고리즘 분석이라고 부른다. 측정할 연산을 먼저 정해야 서로 다른 구현의 숫자를 같은 의미로 읽을 수 있다.

작은 입력 네 개만으로도 차이를 볼 수 있다. 오름차순, 내림차순, 모두 같은 키를 준비한다. 안정성은 키가 전부 같은 기록의 접수 순서로 검사한다. 난수를 사용하지 않으므로 실행할 때마다 같은 입력을 얻는다.

정렬 결과와 안정성을 따로 확인한다

정렬에 사용하는 기준값을 키(key)라고 한다. 이 장에서는 기록의 점수가 키이고, 접수 번호는 기록의 원래 위치를 확인하는 표식이다. 키는 작은 값부터 큰 값으로 정렬한다. 접수 번호를 정렬 기준에 추가하지는 않는다.

안정성(stability)은 키가 같은 항목끼리 입력에서의 상대적인 순서를 유지하는 성질이다. 점수 2인 기록 A가 기록 B보다 먼저 들어왔다면, 안정적인 정렬은 결과에서도 A를 B보다 앞에 둔다. 점수가 다른 두 기록의 순서는 이 성질의 검사 대상이 아니다.

삽입 정렬은 앞부분을 정렬된 상태로 유지하며 새 항목의 자리를 찾는다. 현재 항목보다 키가 큰 원소만 오른쪽으로 민다. 같은 키까지 밀면 나중에 들어온 항목이 먼저 들어온 항목을 추월한다. 따라서 비교 조건의 등호 하나가 안정성을 바꾼다.

병합 정렬은 입력을 작은 구간으로 나누어 정렬한 뒤 합친다. 이미 정렬된 두 구간을 하나로 합치는 과정을 병합(merge)이라고 한다. 양쪽에서 맨 앞에 남은 항목끼리 비교하고 작은 쪽을 결과 배열에 쓴다. 키가 같을 때 왼쪽 항목을 먼저 쓰면 앞서 있던 기록이 먼저 나온다.

완성 코드의 병합 정렬은 재귀 호출을 사용하지 않는다. 재귀는 함수가 자기 자신을 다시 호출하는 방식이다. 여기서는 길이 1인 구간부터 시작해 구간 길이를 2배씩 늘린다. 각 구간은 시작 인덱스를 포함하고 끝 인덱스는 포함하지 않는다. 예를 들어 시작 0, 끝 2인 구간은 인덱스 0과 1을 뜻한다. 이런 경계 표현은 구간 길이를 끝에서 시작을 뺀 값으로 계산하게 해 준다.

퀵 정렬은 기준 항목을 하나 고르고 그보다 작은 쪽과 큰 쪽으로 구간을 나눈다. 이 기준 항목을 피벗(pivot), 기준에 따라 구간을 나누는 작업을 분할(partition)이라고 한다. 이 장에서는 마지막 항목을 피벗으로 고른다. 피벗 이하인 항목을 왼쪽으로 모은 뒤 피벗을 경계에 놓는다. 자리를 확정한 피벗은 다음 처리에서 제외한다.

힙 정렬은 배열을 부모와 자식 관계로 읽는다. 인덱스 i의 왼쪽 자식은 2 * i + 1, 오른쪽 자식은 2 * i + 2다. 각 부모의 키가 자식의 키 이상인 상태를 최대 힙(max heap)이라고 한다. 이 관계가 모든 부모에 성립하면 맨 앞에 가장 큰 키가 있다. 맨 앞 항목을 아직 정렬하지 않은 구간의 마지막으로 보내고, 줄어든 구간에서 관계를 복구한다.

힙을 복구할 때는 두 자식 중 큰 쪽을 고른 뒤 부모와 비교한다. 부모가 더 작으면 자리를 바꾸고 내려간다. 자식이 하나뿐이면 형제 비교를 생략한다. 최대 힙의 전체 기능을 만들 필요는 없다. 여기서는 정렬에 필요한 배열 관계와 아래로 내려가는 연산만 구현한다.

비교 횟수로 비용을 읽는다

입력 크기를 n이라고 하자. 삽입 정렬에서 이미 정렬된 입력은 새 항목마다 바로 앞 항목과 한 번만 비교한다. n이 1 이상이면 총 n - 1번이다. 거꾸로 정렬된 입력은 앞부분을 끝까지 확인하므로 1 + 2 + … + (n - 1)번, 즉 n * (n - 1) / 2번 비교한다.

입력 크기가 커질 때 비용이 어떤 형태로 증가하는지를 나타내는 표기를 빅오 표기법이라고 한다. O(n)은 선형 증가, O(n²)은 제곱에 비례하는 증가의 상한을 표현한다. O(n log n)에서 log는 여기서 2를 밑으로 생각하면 된다. 길이를 계속 절반으로 줄일 때 필요한 단계 수와 연결된다. 빅오는 정확한 횟수나 실행 시간을 뜻하지 않는다.

병합 정렬은 구간 길이를 두 배씩 늘리므로 약 log₂ n단계를 거친다. 한 단계에서 다루는 항목 수는 전체적으로 n에 비례한다. 따라서 전체 비용은 O(n log n)이다. 각 병합에서 한쪽이 먼저 비면 남은 항목은 키 비교 없이 복사한다. 그래서 입력에 따라 비교 횟수는 달라질 수 있다.

퀵 정렬은 분할이 비슷한 크기로 이루어지면 O(n log n) 비용을 기대할 수 있다. 그러나 이번처럼 마지막 원소를 피벗으로 고정하면 정렬된 입력에서는 한쪽 구간이 계속 비게 된다. 비교 횟수는 (n - 1) + (n - 2) + … + 1로 늘어난다. 모두 같은 키도 이 구현에서는 같은 불균형을 만든다.

가능한 입력 중 비용이 가장 큰 경우를 최악의 경우(worst case)라고 한다. 퀵 정렬의 이름만 보고 모든 입력에서 빠를 것이라고 예상하면 안 된다. 피벗을 고르는 방법과 같은 키를 묶는 방법이 실제 동작에 영향을 준다. 이 장에서는 불균형이 비교 횟수로 드러나도록 단순한 분할을 유지한다.

힙 정렬은 부모에서 자식으로 내려갈 때 인덱스가 대략 두 배가 된다. 따라서 한 번 내려가는 경로는 O(log n) 길이다. 가장 큰 항목을 끝으로 보내는 작업을 반복하므로 전체 정렬은 O(n log n)이다. 처음 힙을 만드는 비용은 O(n)이다. 모든 부모가 끝까지 내려가는 것은 아니며, 아래쪽 부모일수록 내려갈 수 있는 거리가 짧기 때문이다.

이번 구현에서 보장하는 성질과 정렬 함수의 추가 저장 공간

정렬	최악의 시간	안정성	추가 공간
삽입	O(n²)	유지	O(1)
병합	O(n log n)	유지	O(n)
퀵	O(n²)	보장하지 않음	O(n)
힙	O(n log n)	보장하지 않음	O(1)

퀵 정렬의 추가 공간은 이 코드가 미처리 구간을 저장할 고정 크기 배열 두 개를 미리 만들기 때문에 O(n)이다. 입력 배열을 복제하는 실험용 공간은 표에서 제외했다. 안정성을 보장하지 않는다는 말은 언제나 동점 순서를 바꾼다는 뜻이 아니다. 한 입력에서 순서를 유지했더라도 다른 입력에서는 바뀔 수 있다는 뜻이다.

실험에서 세는 것은 원소의 키 비교다. 반복문의 인덱스 검사, 배열 대입, 항목 교환은 세지 않는다. 비교가 적더라도 복사가 많으면 실제 실행 시간은 길어질 수 있다. 따라서 횟수 표는 선택한 연산의 비용을 설명하는 자료이며, 전체 실행 시간의 순위표는 아니다.

완성 코드

다음 내용을 main.py로 저장한다. Item은 점수와 접수 번호를 함께 보관한다. Count는 직접 만든 정렬의 비교 횟수를 센다. 내장 정렬은 Item의 비교 메서드를 통해 별도로 센다. 밑줄 두 개로 둘러싸인 __lt__는 Python이 두 객체의 < 비교를 수행할 때 호출하는 특별한 메서드다.

class Item:
    builtin_calls = 0

    def __init__(self, key, order):
        self.key = key
        self.order = order

    def __lt__(self, other):
        Item.builtin_calls += 1
        return self.key < other.key


class Count:
    def __init__(self):
        self.calls = 0

    def less(self, left, right):
        self.calls += 1
        return left.key < right.key


def copy_array(source):
    result = [None] * len(source)
    for i in range(len(source)):
        result[i] = source[i]
    return result


def swap(a, i, j):
    temp = a[i]
    a[i] = a[j]
    a[j] = temp


def insertion_sort(a, count):
    for i in range(1, len(a)):
        item = a[i]
        j = i - 1
        while j >= 0:
            if not count.less(item, a[j]):
                break
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = item


def merge_sort(a, count):
    n = len(a)
    work = [None] * n
    width = 1
    while width < n:
        start = 0
        while start < n:
            middle = min(start + width, n)
            end = min(start + 2 * width, n)
            left = start
            right = middle
            out = start
            while left < middle and right < end:
                if count.less(a[right], a[left]):
                    work[out] = a[right]
                    right += 1
                else:
                    work[out] = a[left]
                    left += 1
                out += 1
            while left < middle:
                work[out] = a[left]
                left += 1
                out += 1
            while right < end:
                work[out] = a[right]
                right += 1
                out += 1
            start = end
        for i in range(n):
            a[i] = work[i]
        width *= 2


def quick_sort(a, count):
    n = len(a)
    if n < 2:
        return
    lows = [0] * n
    highs = [0] * n
    lows[0] = 0
    highs[0] = n - 1
    size = 1
    while size > 0:
        size -= 1
        low = lows[size]
        high = highs[size]
        pivot = a[high]
        boundary = low
        for scan in range(low, high):
            if not count.less(pivot, a[scan]):
                swap(a, boundary, scan)
                boundary += 1
        swap(a, boundary, high)
        if low < boundary - 1:
            lows[size] = low
            highs[size] = boundary - 1
            size += 1
        if boundary + 1 < high:
            lows[size] = boundary + 1
            highs[size] = high
            size += 1


def sift_down(a, root, end, count):
    while 2 * root + 1 < end:
        child = 2 * root + 1
        if child + 1 < end:
            if count.less(a[child], a[child + 1]):
                child += 1
        if not count.less(a[root], a[child]):
            return
        swap(a, root, child)
        root = child


def heap_sort(a, count):
    n = len(a)
    for root in range(n // 2 - 1, -1, -1):
        sift_down(a, root, n, count)
    for end in range(n - 1, 0, -1):
        swap(a, 0, end)
        sift_down(a, 0, end, count)


def make_case(case, n):
    a = [None] * n
    for i in range(n):
        if case == 0:
            key = i + 1
        elif case == 1:
            key = n - i
        else:
            key = 2
        a[i] = Item(key, i)
    return a


def is_ordered(a):
    for i in range(1, len(a)):
        if a[i - 1].key > a[i].key:
            return False
    return True


def same_keys(a, b):
    if len(a) != len(b):
        return False
    for i in range(len(a)):
        if a[i].key != b[i].key:
            return False
    return True


def same_items(a, b):
    if len(a) != len(b):
        return False
    for item in a:
        matches = 0
        for candidate in b:
            if candidate is item:
                matches += 1
        if matches != 1:
            return False
    return True


def equal_order(a):
    text = ""
    for i in range(len(a)):
        if i > 0:
            text += " "
        text += str(a[i].order)
    return text


def check_edges():
    for n in range(2):
        for method in range(4):
            a = make_case(0, n)
            count = Count()
            run_sort(method, a, count)
            assert is_ordered(a)
            assert count.calls == 0


def run_sort(method, a, count):
    if method == 0:
        insertion_sort(a, count)
    elif method == 1:
        merge_sort(a, count)
    elif method == 2:
        quick_sort(a, count)
    else:
        heap_sort(a, count)


def main():
    check_edges()
    print("키 비교 횟수: n=4")
    print("입력 | 삽입 | 병합 | 퀵 | 힙 | 내장")
    for case in range(3):
        source = make_case(case, 4)
        totals = [0] * 4
        for method in range(4):
            a = copy_array(source)
            count = Count()
            run_sort(method, a, count)
            assert is_ordered(a)
            assert same_items(source, a)
            totals[method] = count.calls
        Item.builtin_calls = 0
        reference = sorted(source)
        builtin_total = Item.builtin_calls
        assert is_ordered(reference)
        assert same_items(source, reference)
        for method in range(4):
            a = copy_array(source)
            run_sort(method, a, Count())
            assert same_keys(a, reference)
        if case == 0:
            name = "오름차순"
        elif case == 1:
            name = "내림차순"
        else:
            name = "모두 같음"
        print(
            f"{name} | {totals[0]} | {totals[1]} | "
            f"{totals[2]} | {totals[3]} | {builtin_total}"
        )

    print("모두 같은 키의 접수 순서")
    source = make_case(2, 4)
    for method in range(4):
        a = copy_array(source)
        run_sort(method, a, Count())
        if method == 0:
            name = "삽입"
        elif method == 1:
            name = "병합"
        elif method == 2:
            name = "퀵"
        else:
            name = "힙"
        print(f"{name}: {equal_order(a)}")
    reference = sorted(source)
    print(f"내장: {equal_order(reference)}")
    print("검증: 통과")


if __name__ == "__main__":
    main()

줄별 해설

Item의 key는 비교 대상이고 order는 원래 접수 번호다. 직접 만든 정렬은 Count.less를 통해 key만 비교한다. 이 메서드의 첫 줄에서 calls를 늘리므로 비교가 참이든 거짓이든 한 번으로 센다. 내장 정렬은 __lt__를 호출한다. 두 경로 모두 같은 종류의 키 비교를 세지만 계수는 분리되어 있다.

copy_array는 입력과 같은 길이의 배열을 만들고 각 칸에 항목의 참조를 복사한다. 참조는 객체를 가리키는 값이다. Item 객체 자체를 새로 만들지는 않는다. 정렬 함수들이 Item의 속성을 고치지 않고 배열 칸의 참조만 옮기므로 이 복사로 각 실험의 배치를 독립시킬 수 있다. swap도 객체의 내용을 바꾸지 않고 두 칸의 참조를 교환한다.

insertion_sort의 바깥 반복문이 인덱스 i에 도달하면 그 앞 구간은 이미 정렬되어 있다. item을 잠시 보관한 뒤 큰 항목을 한 칸씩 민다. less(item, a[j])가 거짓이면 앞 항목이 더 작거나 같은 상태다. 여기서 멈추므로 같은 키의 앞 항목을 지나치지 않는다. j가 -1이 되면 배열에 접근하지 않고 반복문을 끝낸다.

merge_sort의 width는 합치기 전 한 구간의 최대 길이다. middle과 end에 min을 쓰는 이유는 마지막 구간이 width보다 짧을 수 있기 때문이다. 두 구간을 합칠 때 오른쪽 키가 더 작은 경우에만 오른쪽을 선택한다. 같으면 else로 가서 왼쪽을 고른다. 한쪽 구간을 모두 소비한 다음에는 나머지를 비교 없이 복사한다.

work를 만든 줄은 한 번만 실행된다. 각 단계에서 work의 모든 유효 칸을 채운 뒤 원본 배열로 복사한다. width가 두 배가 되면 다음 단계는 이전에 정렬한 두 구간을 합친다. 길이가 0이나 1이면 while 조건이 처음부터 거짓이므로 키 비교가 없다.

quick_sort의 lows와 highs는 아직 처리하지 않은 구간의 양 끝을 저장한다. size는 저장된 구간 수이자 다음에 기록할 위치다. 마지막에 저장한 구간부터 꺼내는 방식을 스택이라고 부른다. 여기서는 배열과 정수만으로 필요한 동작을 표현한다. 미처리 구간들은 서로 겹치지 않으므로 길이 n인 배열이면 저장 공간이 충분하다.

boundary 앞에는 피벗 이하인 항목이 모인다. less(pivot, a[scan])를 부정하면 현재 항목이 피벗 이하인지 알 수 있다. 숫자 키만 사용하므로 이 판단이 성립한다. 반복이 끝나면 피벗을 boundary에 놓는다. 그 위치는 확정되었으므로 양쪽 구간만 저장한다. 길이가 0이나 1인 구간은 추가하지 않는다.

sift_down의 end는 힙 구간에 포함하지 않는 끝 인덱스다. child + 1이 end보다 작을 때만 오른쪽 자식을 읽는다. 자식 중 큰 쪽을 고르고 부모가 그 자식 이상이면 멈춘다. 교환했다면 root를 자식 위치로 바꾸어 다음 층을 확인한다. 이 과정에서는 형제를 고르는 비교와 부모를 확인하는 비교를 각각 센다.

heap_sort는 마지막 부모인 n // 2 - 1부터 거꾸로 힙을 만든다. 자식 구간을 먼저 정리해야 부모에서 내려갈 때 그 아래의 관계를 이용할 수 있다. 두 번째 반복문은 맨 앞의 최댓값을 end로 옮긴다. 다음 복구에서는 end를 제외하므로 뒤에 확정한 항목을 다시 건드리지 않는다.

is_ordered는 인접한 키의 역전 여부를 확인한다. 이것만으로는 원소를 잃어버린 오류를 찾을 수 없다. 그래서 same_items가 원래 객체가 결과에 정확히 한 번씩 있는지도 검사한다. is는 두 참조가 같은 객체를 가리키는지 확인하는 연산자다. 이 검증 함수는 서로 다른 Item 객체로 구성한 이번 입력을 전제로 한다.

same_items의 이중 반복 비용은 O(n²)이지만 정렬 비교 계수에는 들어가지 않는다. 검증 비용과 측정 대상 비용을 구별하기 위해서다. assert는 조건이 거짓일 때 실행을 중단하는 검증 문장이다. 일반 실행에서는 검증하지만 Python을 -O 옵션으로 실행하면 생략될 수 있으므로 안내한 명령 그대로 실행한다.

main은 같은 source를 매번 복사하여 네 정렬에 전달한다. 앞선 정렬의 결과를 다음 정렬에 그대로 넘기면 입력 조건이 달라지기 때문이다. totals에 비교 횟수를 보관한 뒤 마지막 비교 단계에서만 sorted를 사용한다. sorted는 새 리스트를 반환하는 내장 정렬이다. 직접 구현하는 부분에서는 사용하지 않았다.

실행 결과

다음은 CPython 3.12에서의 예상 출력이다. 직접 만든 네 정렬의 횟수는 코드의 비교 규칙으로 결정된다. 내장 정렬의 정확한 비교 횟수는 Python의 구현과 버전이 보장하는 인터페이스가 아니므로 다른 실행 환경에서는 달라질 수 있다. 내장 정렬의 결과와 안정성은 비교 횟수와 구분해 확인한다.

python3 main.py

키 비교 횟수: n=4
입력 | 삽입 | 병합 | 퀵 | 힙 | 내장
오름차순 | 3 | 4 | 6 | 7 | 3
내림차순 | 6 | 4 | 6 | 6 | 3
모두 같음 | 3 | 4 | 6 | 6 | 3
모두 같은 키의 접수 순서
삽입: 0 1 2 3
병합: 0 1 2 3
퀵: 0 1 2 3
힙: 1 2 3 0
내장: 0 1 2 3
검증: 통과

삽입 정렬의 오름차순 3회와 내림차순 6회는 각각 n - 1과 n * (n - 1) / 2에 n=4를 대입한 결과다. 병합 정렬은 이번 세 입력에서 모두 4회다. 길이 1인 두 구간을 합칠 때 각각 1회씩, 길이 2인 두 구간을 합칠 때 2회 비교한다. 다른 배치에서는 마지막 병합에 3회가 필요할 수도 있다.

힙 정렬의 오름차순 7회는 힙을 만드는 4회와 추출 중 복구하는 3회의 합이다. 모두 같은 입력에서는 복구 과정의 교환을 일찍 멈추지만, 최댓값을 끝으로 보내는 교환 자체가 동점 순서를 바꾼다. 비교 횟수가 적다는 사실과 안정성은 별개의 성질이다.

퀵 정렬은 모두 같은 입력에서 접수 순서를 유지했다. 그러나 키가 2, 2, 1인 입력에 접수 번호 0, 1, 2를 붙여 실행하면 결과의 접수 번호는 2, 1, 0이 된다. 마지막 피벗 1을 맨 앞으로 옮기는 교환이 앞의 두 동점 기록을 뒤집기 때문이다. 안정성은 유리한 예 하나로 증명할 수 없다.

내장 정렬은 안정성을 보장한다. 실제 작업에서는 검증된 내장 정렬을 우선 검토하고, 직접 구현한 코드는 동작을 이해하고 특별한 제약을 실험하는 데 사용한다. 보장 사항은 Python의 sorted 설명에서 확인할 수 있다. 내장 정렬의 짧은 실행 경로를 이 장의 네 구현 중 하나와 동일하다고 가정하지 않는다.

실무에서 자주 틀리는 것

같은 키까지 오른쪽으로 민다

삽입 정렬에서 다음 조건은 앞 항목이 현재 항목 이상일 때 이동시킨다. 키는 정렬되지만 같은 키의 순서가 뒤집힐 수 있다.

# 틀린 코드: 같은 키도 이동시킨다.
if not count.less(a[j], item):
    a[j + 1] = a[j]

# 고친 코드: 현재 항목보다 큰 키만 이동시킨다.
if count.less(item, a[j]):
    a[j + 1] = a[j]

조건만 바꾸고 나머지 제어 흐름을 빼먹지 않아야 한다. 완성 코드처럼 이동하지 않을 때는 break로 멈추고, 마지막에 보관한 item을 빈 자리에 넣는다.

병합에서 동점이면 오른쪽을 먼저 쓴다

작은 쪽을 고른다는 설명만으로는 동점 처리가 정해지지 않는다. 다음의 틀린 조건은 같은 키일 때 else에서 오른쪽을 고르게 만든다.

# 틀린 코드: 동점이면 오른쪽으로 간다.
if count.less(a[left], a[right]):
    work[out] = a[left]
else:
    work[out] = a[right]

# 고친 코드: 오른쪽이 더 작을 때만 오른쪽을 고른다.
if count.less(a[right], a[left]):
    work[out] = a[right]
else:
    work[out] = a[left]

실제 병합에서는 선택한 쪽의 인덱스도 함께 늘린다. 완성 코드의 두 분기를 한 쌍으로 읽어야 같은 항목을 반복해서 복사하는 오류를 피할 수 있다.

퀵 정렬에서 확정된 피벗을 다시 처리한다

피벗을 boundary에 놓은 뒤 왼쪽 구간 끝을 boundary로 지정하면 피벗을 다시 포함한다. 피벗이 매번 마지막에 놓이는 입력에서는 구간 크기가 줄지 않아 반복이 끝나지 않을 수 있다.

# 틀린 코드
highs[size] = boundary

# 고친 코드
highs[size] = boundary - 1

오른쪽 시작도 boundary + 1이어야 한다. 분할이 끝날 때마다 피벗 하나는 다음 작업에서 빠진다는 사실을 경계식으로 확인한다.

비교 함수를 두 번 호출해 계수를 부풀린다

진단 메시지에 비교 결과를 표시하려고 같은 함수를 다시 호출하면 실제 분기와 무관한 비교가 추가된다. 상태를 바꾸는 계수 함수를 단순 조회 함수처럼 사용하지 않는다.

# 틀린 코드
print(count.less(item, a[j]))
if count.less(item, a[j]):
    a[j + 1] = a[j]

# 고친 코드
should_move = count.less(item, a[j])
print(should_move)
if should_move:
    a[j + 1] = a[j]

이 코드는 디버깅할 때의 수정 예다. 완성 코드의 결정적인 출력 형식을 유지하려면 진단용 print는 제거한다. 측정하는 연산이 정확히 한 번 실행되는지는 출력문을 추가할 때도 확인해야 한다.

한눈에 보기

구현을 읽을 때 확인할 기준과 코드로 확인한 결과

대상	핵심 기준	이번 실험의 관찰	주의점
삽입 정렬	큰 항목만 오른쪽으로 이동	오름차순 3회, 내림차순 6회	역순에서는 이동도 많다
병합 정렬	동점이면 왼쪽 먼저	세 입력 모두 4회	별도 작업 배열이 필요하다
퀵 정렬	피벗을 다음 구간에서 제외	세 입력 모두 6회	마지막 피벗은 편향될 수 있다
힙 정렬	큰 자식과 부모를 비교	동점 접수 순서가 바뀐다	키 순서와 안정성을 구별한다
내장 정렬	같은 키와 같은 입력 사용	이번 환경에서 세 입력 모두 3회	정확한 횟수는 구현에 의존한다

배열이 정렬되어 있다는 것은 현재 배치에 관한 성질이다. 이후 항목을 추가하면 그 성질을 유지하기 위한 작업이 필요하다. 다음 장에서는 값을 정렬된 관계로 넣고 찾기 위해 이진 탐색 트리를 직접 만든다.

연습 문제

1. main에서 비교 표에 사용하는 make_case(case, 4)를 make_case(case, 8)로 바꾸고 제목의 n도 고친다. 오름차순과 내림차순에서 삽입 정렬과 퀵 정렬의 비교 횟수를 먼저 계산한 뒤 실행으로 확인한다.
2. 모두 같은 키의 접수 순서를 출력하는 부분에서 입력을 키 2, 2, 1인 세 기록으로 바꾼다. 퀵 정렬이 동점 순서를 바꾸는지 확인하고, 어떤 교환에서 바뀌는지 설명한다.
3. merge_sort에서 동점일 때 오른쪽 항목을 먼저 선택하도록 조건을 바꾼다. 모두 같은 키 네 개의 접수 순서와 키 비교 횟수가 어떻게 되는지 확인한다.
4. Count에 swaps 속성을 추가하고 힙 정렬의 교환 횟수를 센다. 같은 인덱스끼리의 교환도 호출 한 번으로 세는 규칙을 사용한다. 모두 같은 키 네 개에서 키 비교와 교환 횟수를 각각 구한다.

정답과 해설

1. n=8에서 삽입 정렬의 오름차순은 7회이고 내림차순은 28회다. 이번 퀵 정렬은 두 입력 모두 28회다. 다음 식은 반복해서 더한 값과 같은 결과를 낸다.

   n = 8
   print(n - 1)
   print(n * (n - 1) // 2)
   

   출력은 차례로 7과 28이다. //는 정수 나눗셈이다. 표의 한 행만 보고 일반적인 증가 형태를 판단하지 말고, n을 바꿨을 때 예측식과 계수가 함께 맞는지 확인한다.

2. 입력은 다음처럼 만든다. 출력 부분의 source 생성 줄을 바꾸면 된다.

   source = [None] * 3
   source[0] = Item(2, 0)
   source[1] = Item(2, 1)
   source[2] = Item(1, 2)
   

   퀵 정렬의 접수 순서는 2 1 0이다. 첫 분할에서는 피벗 1 이하인 앞 항목이 없다. 마지막 교환이 인덱스 0과 2를 바꾸어 키 2인 접수 번호 0을 뒤로 보낸다. 남은 두 동점 항목은 그 순서를 유지하므로 뒤집힌 상대 순서가 그대로 남는다.

3. 병합의 선택 조건을 다음처럼 바꾼다. 선택한 인덱스의 증가도 해당 분기에 맞춰 둔다.

   if count.less(a[left], a[right]):
       work[out] = a[left]
       left += 1
   else:
       work[out] = a[right]
       right += 1
   

   모두 같은 키 네 개에서는 접수 순서가 3 2 1 0이 되고 비교는 여전히 4회다. 첫 단계에서 각 쌍이 뒤집히고, 다음 단계에서는 오른쪽 쌍 전체가 먼저 나온다. 키 비교 횟수가 같아도 안정성은 달라질 수 있다.

4. Count.__init__에 self.swaps = 0을 추가한다. 힙 정렬과 sift_down의 swap 호출을 아래 함수 호출로 교체한다. 다른 정렬의 swap 호출은 그대로 두어도 된다.

   def heap_swap(a, i, j, count):
       count.swaps += 1
       swap(a, i, j)
   

   모두 같은 키 네 개에서 키 비교는 6회, 교환은 3회다. 힙을 만들거나 아래로 내려가는 과정에서는 키가 같아 교환하지 않는다. 그러나 heap_sort의 두 번째 반복문은 끝 인덱스 3, 2, 1에 대해 맨 앞 항목을 각각 교환한다. 바로 이 세 교환이 접수 순서를 바꾼다.