버블·선택 정렬의 확정된 구간

정렬(sorting)은 값들을 정해진 순서로 다시 늘어놓는 일입니다. 이진 탐색처럼 정렬된 입력을 전제로 하는 알고리즘이 많아서, 정렬은 알고리즘 공부에서 가장 먼저 만나는 큰 주제입니다. 실제 프로그램에서는 Python의 sorted처럼 이미 잘 만들어진 정렬을 쓰지만, 단순한 정렬을 직접 짜 보면 반복 한 차례가 무엇을 해내는지, 그것이 왜 전체를 정렬로 이끄는지를 따지는 연습을 할 수 있습니다. 이 글에서는 가장 단순한 두 방법인 버블 정렬과 선택 정렬을 만들고, 차례가 끝날 때마다 어느 자리가 확정되는지를 중심으로 둘을 비교합니다.

정렬이 해야 하는 일

정렬의 입력은 서로 크기를 비교할 수 있는 값들의 리스트이고, 출력은 같은 값들을 작은 것부터 늘어놓은 리스트입니다. 여기서 "같은 값들"이라는 조건이 중요합니다. [3, 1, 3]을 정렬한 결과는 [1, 3, 3]이어야 하며, 순서가 맞더라도 3 하나가 빠진 [1, 3]은 정렬한 결과가 아닙니다. 같은 값이 여러 번 나올 수 있으므로, 엄밀히는 앞의 값이 뒤의 값보다 크지 않은 순서, 곧 비내림차순(non-decreasing order)으로 늘어놓는다고 말합니다.

이 글의 함수들은 입력 리스트를 복사해서 정렬한 뒤 새 리스트를 돌려주고, 원래 리스트는 그대로 둡니다. 복사에 O(n)이 더 들지만, 정렬 전후를 나란히 출력해 비교하기 쉽습니다.

버블 정렬: 큰 값이 오른쪽으로 밀려난다

버블 정렬(bubble sort)은 왼쪽부터 이웃한 두 값을 비교해, 왼쪽 값이 더 크면 둘을 맞바꿉니다. 이것을 처리할 구간의 끝까지 한 번 하는 것을 한 차례라고 부르겠습니다. [4, 2, 3, 1]의 첫 차례는 다음과 같습니다.

첫 비교에서 4가 2보다 커서 오른쪽으로 옮겨 가고, 그다음 비교에서도 계속 더 크기 때문에 끝까지 밀려갑니다. 일반적으로 한 차례 동안 지금까지 본 가장 큰 값이 비교할 때마다 한 칸씩 오른쪽으로 옮겨지므로, 차례가 끝나면 처리한 구간의 최댓값이 그 구간의 맨 오른쪽에 놓입니다. 물속의 거품이 떠오르듯 큰 값이 끝으로 올라간다고 해서 버블 정렬이라는 이름이 붙었습니다.

맨 오른쪽 칸에는 이제 최댓값이 들어 있으므로 다시 볼 필요가 없습니다. 다음 차례는 앞쪽 세 칸만 같은 방식으로 처리해 그중 최댓값을 오른쪽에서 두 번째 칸에 놓고, 그다음 차례는 앞쪽 두 칸을 처리합니다. 이렇게 차례가 하나 끝날 때마다 오른쪽 끝에서부터 자리가 하나씩 확정됩니다.

원소가 n개이면 n - 1차례면 충분합니다. 나머지 칸이 모두 확정되고 나면 마지막에 남은 맨 왼쪽 칸에는 가장 작은 값이 남기 때문입니다.

차례를 다 채우기 전에 멈출 수 있는 경우도 있습니다. 한 차례 동안 한 번도 바꾸지 않았다면 처리한 구간의 이웃한 쌍이 모두 순서대로라는 뜻이고, 그 오른쪽은 이미 확정된 칸이므로 리스트 전체가 정렬되어 있습니다. 뒤의 코드에서는 changed 변수로 이것을 확인합니다.

선택 정렬: 남은 값 중 가장 작은 값을 고른다

선택 정렬(selection sort)은 반대쪽에서 자리를 확정합니다. 아직 확정되지 않은 구간 전체에서 최솟값을 찾아, 그 구간의 첫 칸과 맞바꿉니다. 첫 차례에는 리스트 전체에서 최솟값을 찾아 0번 칸에 놓고, 다음 차례에는 1번 칸부터 끝까지에서 최솟값을 찾아 1번 칸에 놓는 식입니다. 차례 하나가 끝날 때마다 왼쪽 끝에서부터 자리가 하나씩 확정됩니다.

[4, 2, 3, 1]은 첫 차례 만에 정렬되었지만, 선택 정렬은 그 사실을 알지 못하고 나머지 차례에서도 최솟값을 찾는 비교를 모두 합니다. 남은 구간의 최솟값이 무엇인지는 구간 전체를 보기 전까지 알 수 없기 때문입니다. 2, 3차례처럼 찾은 최솟값이 이미 구간의 첫 칸에 있으면 바꿀 필요가 없으므로, 코드에서는 위치가 다를 때만 바꾸도록 했습니다.

두 정렬을 코드로 옮기기

버블 정렬의 바깥 반복 변수 end는 n - 1부터 1까지 줄어들며 이번 차례에 처리할 구간의 마지막 칸을 나타내고, 안쪽 반복은 i번과 i + 1번 칸을 비교합니다. 선택 정렬의 smallest는 이번 차례에서 지금까지 찾은 최솟값의 위치입니다.

def bubble_sort(values):
    result = list(values)
    for end in range(len(result) - 1, 0, -1):
        changed = False
        for i in range(end):
            if result[i] > result[i + 1]:
                result[i], result[i + 1] = result[i + 1], result[i]
                changed = True
        if not changed:
            break
    return result


def selection_sort(values):
    result = list(values)
    for i in range(len(result) - 1):
        smallest = i
        for j in range(i + 1, len(result)):
            if result[j] < result[smallest]:
                smallest = j
        if smallest != i:
            result[i], result[smallest] = result[smallest], result[i]
    return result


values = [4, 2, 3, 1]
print(bubble_sort(values))
print(selection_sort(values))
print(values)
print(bubble_sort([]), selection_sort([7]))

[1, 2, 3, 4]
[1, 2, 3, 4]
[4, 2, 3, 1]
[] [7]

두 함수의 결과는 같고, 세 번째 줄에서 보듯 원래 리스트는 바뀌지 않습니다. 빈 리스트와 원소가 하나인 리스트에서는 바깥 반복이 한 번도 돌지 않고 복사한 리스트를 그대로 돌려줍니다. 원소가 하나 이하라면 이미 정렬되어 있으므로 이것이 맞는 결과입니다.

왜 정렬되는가

두 방법 모두 차례마다 참인 사실로 정확성을 설명할 수 있습니다. 버블 정렬에서는 k차례가 끝나면 오른쪽 끝의 k칸에 가장 큰 k개의 값이 크기순으로 들어 있습니다. 첫 차례가 최댓값을 맨 끝으로 보낸다는 것은 앞에서 보았고, 다음 차례도 남은 칸에서 같은 일을 하므로 확정된 칸이 하나씩 늘어납니다. 확정된 칸의 값들은 남은 칸의 어떤 값보다도 작지 않으므로, 이후의 차례가 그 칸을 건드리지 않아도 순서가 맞습니다.

선택 정렬에서는 k차례가 끝나면 왼쪽 끝의 k칸에 가장 작은 k개의 값이 크기순으로 들어 있습니다. 매 차례 남은 값 중 가장 작은 값을 확정된 칸 바로 다음에 놓기 때문입니다. 두 방법 모두 값을 맞바꾸기만 하므로 리스트에 든 값의 종류와 개수는 그대로이고, 반복 범위가 모두 정해져 있으므로 두 함수는 늘 끝납니다.

비교와 교환 횟수 세기

두 방법이 실제로 몇 번 비교하고 몇 번 바꾸는지 세어 보겠습니다. 아래 코드는 앞의 두 함수에 횟수를 세는 변수를 더하고, 비교를 위해 역순 쌍이라는 값도 함께 셉니다. 역순 쌍(inversion)은 앞에 있는 값이 뒤에 있는 값보다 큰 위치의 쌍입니다. [3, 1, 2]에서는 (3, 1)과 (3, 2)가 역순 쌍이고 (1, 2)는 아니므로 역순 쌍이 2개입니다. 정렬된 리스트에는 역순 쌍이 없으므로, 역순 쌍의 개수는 리스트가 정렬된 상태에서 얼마나 멀리 있는지를 나타냅니다.

def bubble_counts(values):
    result = list(values)
    comparisons = swaps = 0
    for end in range(len(result) - 1, 0, -1):
        changed = False
        for i in range(end):
            comparisons += 1
            if result[i] > result[i + 1]:
                result[i], result[i + 1] = result[i + 1], result[i]
                swaps += 1
                changed = True
        if not changed:
            break
    return result, comparisons, swaps


def selection_counts(values):
    result = list(values)
    comparisons = swaps = 0
    for i in range(len(result) - 1):
        smallest = i
        for j in range(i + 1, len(result)):
            comparisons += 1
            if result[j] < result[smallest]:
                smallest = j
        if smallest != i:
            result[i], result[smallest] = result[smallest], result[i]
            swaps += 1
    return result, comparisons, swaps


def inversions(values):
    count = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] > values[j]:
                count += 1
    return count


for values in [[1, 2, 3, 4, 5, 6], [6, 5, 4, 3, 2, 1], [4, 2, 6, 1, 5, 3]]:
    _, bc, bs = bubble_counts(values)
    _, sc, ss = selection_counts(values)
    print(values, "버블", bc, bs, "선택", sc, ss, "역순 쌍", inversions(values))

[1, 2, 3, 4, 5, 6] 버블 5 0 선택 15 0 역순 쌍 0
[6, 5, 4, 3, 2, 1] 버블 15 15 선택 15 3 역순 쌍 15
[4, 2, 6, 1, 5, 3] 버블 14 8 선택 15 2 역순 쌍 8

두 정렬 뒤의 숫자는 비교 횟수와 교환 횟수 순서입니다. _는 정렬 결과처럼 받기는 하지만 쓰지 않을 값에 관례상 붙이는 이름입니다.

선택 정렬의 비교 횟수는 입력과 상관없이 15번입니다. 차례마다 남은 칸 수보다 하나 적게 비교하므로 5 + 4 + 3 + 2 + 1 = 15, 일반적으로 n(n - 1)/2번입니다. 대신 교환은 차례마다 많아야 한 번이라 n - 1번을 넘지 않습니다. 역순 입력에서 3번인 것은 6과 1, 5와 2, 4와 3을 한 번씩 바꾸면 끝나기 때문입니다.

버블 정렬은 입력에 따라 크게 달라집니다. 이미 정렬된 입력에서는 첫 차례의 비교 5번 뒤에 바꾼 것이 없어 바로 멈추고, 역순 입력에서는 매 차례 모든 쌍을 바꾸어 비교와 교환이 모두 15번입니다. 눈여겨볼 것은 교환 횟수가 마지막 열의 역순 쌍 개수와 늘 같다는 점입니다.

더 깊이: 이웃 교환 한 번은 역순 쌍을 하나만 없앤다

버블 정렬의 교환 횟수가 역순 쌍의 개수와 같은 이유는 다음과 같습니다. 이웃한 두 값 a와 b에서 a가 b보다 커서 둘을 맞바꾸면, 이 두 값 사이의 앞뒤 관계만 바뀌고 다른 어떤 두 값의 앞뒤 관계도 바뀌지 않습니다. 다른 값 c는 a와 b 둘 모두보다 앞에 있거나 둘 모두보다 뒤에 있었고, 교환 뒤에도 그렇기 때문입니다. 그래서 교환 한 번으로 역순 쌍은 정확히 하나 줄고, 정렬이 끝나면 역순 쌍이 0개이므로 교환 횟수는 처음 역순 쌍의 개수와 같습니다.

이 사실은 이웃한 값끼리만 바꾸는 모든 정렬에 적용됩니다. 역순 입력에서는 모든 쌍, 곧 n(n - 1)/2개가 역순 쌍이므로 이웃 교환만 쓰는 정렬은 이런 입력에서 적어도 그만큼 바꿔야 합니다. 값이 모두 다른 무작위 순서에서는 각 쌍이 역순일 확률이 1/2이라서 역순 쌍이 평균 n(n - 1)/4개이고, 평균적으로도 Θ(n²)번을 바꿔야 합니다. 5장의 병합 정렬과 퀵 정렬이 더 빠를 수 있는 것은, 값을 멀리 떨어진 자리로 옮겨 한 번에 여러 역순 쌍을 없앨 수 있기 때문입니다.

같은 값의 순서와 안정성

학생 기록을 점수로 정렬하는 것처럼, 정렬 기준이 되는 값 외에 다른 정보가 붙어 있는 경우를 생각해 봅시다. 정렬 기준이 되는 값을 키(key)라고 합니다. 키가 같은 기록들이 정렬 뒤에도 원래의 앞뒤 순서를 유지한다면 그 정렬을 안정 정렬(stable sort)이라고 합니다. 숫자만 정렬하면 같은 값끼리 자리가 바뀌어도 눈으로 구별할 수 없으므로, 확인할 때는 값에 이름표를 붙인 튜플을 쓰고 첫 번째 값만 비교합니다. 간단히 하려고 버블 정렬의 조기 종료는 뺐습니다.

def bubble_by_key(records):
    result = list(records)
    for end in range(len(result) - 1, 0, -1):
        for i in range(end):
            if result[i][0] > result[i + 1][0]:
                result[i], result[i + 1] = result[i + 1], result[i]
    return result


def selection_by_key(records):
    result = list(records)
    for i in range(len(result) - 1):
        smallest = i
        for j in range(i + 1, len(result)):
            if result[j][0] < result[smallest][0]:
                smallest = j
        if smallest != i:
            result[i], result[smallest] = result[smallest], result[i]
    return result


records = [(2, "가"), (2, "나"), (1, "다")]
print(bubble_by_key(records))
print(selection_by_key(records))

[(1, '다'), (2, '가'), (2, '나')]
[(1, '다'), (2, '나'), (2, '가')]

버블 정렬은 왼쪽 값이 더 클 때만, 곧 >가 참일 때만 바꾸므로 키가 같은 이웃은 바꾸지 않습니다. 키가 같은 두 기록이 서로를 지나칠 방법이 없어서 "가"가 "나"보다 앞이라는 원래 순서가 유지됩니다. 선택 정렬은 첫 차례에 0번 칸의 (2, "가")를 멀리 떨어진 (1, "다")와 맞바꾸면서 (2, "가")를 (2, "나")의 뒤로 보내 버렸습니다. 이처럼 멀리 떨어진 값을 바꾸는 정렬은 키가 같은 기록의 순서를 뒤집을 수 있어서 일반적으로 안정 정렬이 아닙니다. 안정성이 실제로 어디에 쓰이는지는 정렬의 정답 조건·안정성·시간 측정에서 여러 기준으로 정렬하며 다룹니다.

두 정렬의 비용

두 방법 모두 최악의 경우 Θ(n²)이라 큰 입력에는 맞지 않습니다. 원소가 1만 개만 되어도 비교가 약 5천만 번입니다. 선택 정렬은 비교가 많지만 교환이 적어서, 값을 옮겨 쓰는 비용이 비교보다 훨씬 큰 상황에서는 장점이 될 수 있습니다. 버블 정렬은 거의 정렬된 입력에서 빨리 끝나지만, 다음 글의 삽입 정렬이 같은 장점을 더 적은 작업으로 얻습니다. 추가 공간은 두 방법 모두 변수 몇 개뿐인 O(1)이고, 이 글의 함수는 원본을 남기려는 복사 때문에 O(n)을 더 씁니다.

정리

• 정렬의 결과는 입력과 같은 값들을 비내림차순으로 늘어놓은 것이어야 합니다.
• 버블 정렬은 이웃한 두 값을 비교해 바꾸며, 한 차례가 끝날 때마다 남은 값 중 최댓값이 오른쪽 끝에 확정됩니다. 바꾼 것이 없는 차례가 나오면 바로 멈출 수 있습니다.
• 선택 정렬은 남은 구간에서 최솟값을 찾아 그 구간의 첫 칸과 바꾸며, 한 차례마다 왼쪽 끝에서부터 자리가 확정됩니다.
• 버블 정렬의 교환 횟수는 역순 쌍의 개수와 같습니다. 선택 정렬은 비교가 늘 n(n - 1)/2번이지만 교환은 많아야 n - 1번입니다.
• 버블 정렬은 키가 같은 값의 순서를 유지하는 안정 정렬이고, 멀리 떨어진 값을 바꾸는 선택 정렬은 일반적으로 안정 정렬이 아닙니다.

연습 문제

1. 버블 정렬 따라가기

[3, 1, 2]를 버블 정렬할 때 차례마다 리스트가 어떻게 바뀌는지 쓰고, 비교 횟수와 교환 횟수를 구하세요. 조기 종료는 언제 일어나나요?

2. 선택 정렬이 뒤집는 순서

본문의 selection_by_key로 [(3, "가"), (1, "나"), (3, "다"), (2, "라")]를 정렬하면 결과는 무엇인가요? 키가 3인 "가"와 "다"의 순서는 어떻게 되나요?

3. 버블 정렬의 비교를 >=로 바꾸면

버블 정렬의 result[i] > result[i + 1]을 result[i] >= result[i + 1]로 바꾸면 안정성과 조기 종료는 어떻게 될까요? [7, 7, 7]을 예로 생각해 보세요.

다음 글 삽입 정렬과 이미 정렬된 앞부분에서는 왼쪽 구간을 정렬된 채로 유지하면서 새 값을 하나씩 끼워 넣는 방법을 봅니다.