버블 정렬, 선택 정렬, 삽입 정렬 비교하기

기본 정렬을 외우기보다는, 반복 범위와 교환 시점 그리고 break가 가능한 이유를 비교하면서 다시 정리한 글입니다.

개요

정렬은 알고리즘을 공부할 때 자주 나오는 기본 개념입니다. 블로그에 알고리즘을 적게 된 중요한 이유는, 이번에도 확실하게 잡지 않고 대충 넘어가면 반복 범위나 교환 시점처럼 작은 부분에서 다시 헷갈릴 수 있다고 생각했기 때문입니다. 그래서 단순히 "버블 정렬은 O(n²)입니다"처럼 외우기보다는, 왜 반복 범위가 그렇게 잡히는지, 언제 비교를 멈출 수 있는지, 교환이 어디서 일어나는지를 확실하게 짚고 넘어가려고 합니다.

세 정렬을 비교해서 보고 싶었던 부분

이번에 다시 보면서 가장 헷갈렸던 부분은 세 가지였습니다.

• 반복 범위를 왜 n - 1까지만 도는지
• 값을 언제 교환하는지
• break로 조기 종료할 수 있는지

세 정렬은 모두 새로운 배열을 만들지 않고 원본 배열 안에서 값을 바꾸는 방식이라 공간 복잡도는 O(1)입니다. 하지만 값을 비교하고 교환하는 방식은 조금씩 다릅니다.

[5, 4, 9, 1, 3]으로 흐름 보기

같은 배열을 기준으로 보면 세 정렬의 차이가 더 잘 보입니다. Bubble Sort는 큰 값이 오른쪽으로 밀려나고, Selection Sort는 최솟값을 끝까지 찾은 뒤 한 번 교환하고, Insertion Sort는 현재 값을 왼쪽의 정렬된 영역에 끼워 넣습니다.

노란색은 비교 중인 값, 파란색은 자리가 확정된 값입니다.

Bubble Sort

Bubble Sort는 이웃한 두 값을 비교해 앞의 값이 더 크면 교환합니다. 한 바퀴가 끝날 때마다 현재 구간에서 가장 큰 값이 오른쪽 끝에 자리 잡습니다.

def bubble_sort(array):
    n = len(array)

    for i in range(n - 1):
        for j in range(n - 1 - i):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]

    return array

여기서 반복 범위가 처음에는 헷갈렸습니다.

for i in range(n - 1):
    for j in range(n - 1 - i):

바깥쪽 반복이 n - 1번인 이유는 앞의 n - 1개 원소가 정렬되면 마지막 원소는 자동으로 제자리에 있기 때문입니다.

안쪽 반복에서 -1과 -i의 역할은 다릅니다.

• -1: j + 1이 배열 범위를 벗어나지 않게 합니다
• -i: 오른쪽에 이미 정렬된 원소를 비교 대상에서 제외합니다

길이가 5인 배열이라면 비교 범위는 다음처럼 줄어듭니다.

한 바퀴마다 가장 큰 값 하나가 오른쪽에 확정되기 때문에 비교 범위도 하나씩 줄어듭니다.

Bubble Sort에서 break가 가능한 경우

처음 구현한 Bubble Sort에는 조기 종료가 없습니다. 그래서 [1, 2, 3, 4, 5]처럼 이미 정렬된 배열도 반복문이 끝까지 실행됩니다.

하지만 한 바퀴 전체에서 교환이 한 번도 일어나지 않았다면 배열이 이미 정렬된 상태라고 볼 수 있습니다.

def bubble_sort(array):
    n = len(array)

    for i in range(n - 1):
        swapped = False

        for j in range(n - 1 - i):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                swapped = True

        if not swapped:
            break

    return array

이미 정렬된 배열에서는 첫 바퀴에 n - 1번만 비교하고 종료하므로 최선 시간 복잡도가 O(n)이 됩니다. 평균과 최악은 여전히 O(n²)입니다.

단순히 이웃한 한 쌍이 정렬되어 있다고 바로 break하면 안 됩니다. [1, 3, 2]는 첫 비교에서 1 < 3이지만 뒤의 3, 2는 정렬되지 않았습니다. 따라서 한 번의 비교가 아니라 한 바퀴 전체에서 교환이 없었는지를 봐야 합니다.

Selection Sort

Selection Sort는 남은 구간에서 최솟값을 찾고, 탐색이 끝난 뒤 현재 위치와 한 번 교환합니다.

처음에는 더 작은 값을 만날 때마다 바로 교환하는 방식으로 작성했습니다.

def selection_sort(array):
    n = len(array)

    for i in range(n):
        min_index = i

        for j in range(i + 1, n):
            if array[min_index] > array[j]:
                array[min_index], array[j] = array[j], array[min_index]

    return array

이 코드도 정렬 결과는 올바릅니다. 더 작은 값을 만날 때마다 즉시 교환하므로 내부 반복이 끝나면 가장 작은 값이 현재 위치에 남습니다.

하지만 전형적인 Selection Sort와는 교환 시점이 다릅니다.

• min_index가 계속 i인 채로 바뀌지 않습니다
• 더 작은 값을 발견할 때마다 바로 교환합니다
• 최악의 경우 교환이 O(n²)번 발생할 수 있습니다

즉, 정렬에 실패한 코드는 아니지만 일반적인 Selection Sort보다는 Exchange Sort에 가까운 구현이었습니다.

Selection Sort로 작성하려면 탐색 중에는 최솟값의 인덱스만 기록하고, 탐색이 끝난 뒤 한 번만 교환해야 합니다.

def selection_sort(array):
    n = len(array)

    for i in range(n - 1):
        min_index = i

        for j in range(i + 1, n):
            if array[j] < array[min_index]:
                min_index = j

        array[i], array[min_index] = array[min_index], array[i]

    return array

처음 코드에서 바뀐 핵심은 다음 두 부분입니다.

# 탐색 중에는 인덱스만 변경합니다
min_index = j

# 탐색이 끝난 뒤 한 번 교환합니다
array[i], array[min_index] = array[min_index], array[i]

range(i + 1, n)은 현재 위치 i 다음부터 마지막까지 탐색한다는 뜻입니다. 현재 위치 i는 이미 최솟값 후보로 잡아두었기 때문에 자기 자신을 다시 비교할 필요는 없습니다.

Selection Sort는 왜 break로 개선하기 어려울까

Selection Sort는 입력이 이미 정렬되어 있어도 남은 구간 전체를 확인해야 합니다.

[1, 3, 2]

i = 0일 때 1은 이미 최솟값이므로 교환하지 않습니다. 하지만 뒤의 [3, 2]는 아직 정렬되지 않았습니다. 현재 위치에서 교환이 없었다는 사실만으로 뒤쪽 영역까지 정렬되었다고 판단할 수는 없습니다.

그래서 일반적인 Selection Sort는 최선, 평균, 최악 모두 O(n²)입니다. 대신 정석적인 Selection Sort는 한 바퀴에 최대 한 번만 교환하므로 교환 횟수는 최대 n - 1번입니다.

Insertion Sort

Insertion Sort는 현재 원소를 왼쪽의 이미 정렬된 영역에 끼워 넣는 방식입니다.

처음에는 현재 원소를 계속 array[i]와 비교했습니다.

def insertion_sort(array):
    n = len(array)

    for i in range(1, n):
        for j in range(i - 1, -1, -1):
            if array[j] > array[i]:
                array[j], array[i] = array[i], array[j]

    return array

문제는 한 번 교환한 뒤에도 계속 array[i]를 사용한다는 점이었습니다.

[4, 6, 2, 9, 1]

i = 2에서 6과 2를 교환하면 [4, 2, 6, 9, 1]이 됩니다. 이동 중인 2는 이제 인덱스 1에 있지만, 다음 반복에서도 인덱스 2의 6을 비교하게 됩니다. 그래서 4와 2를 비교하지 못합니다.

여기서 i와 j의 역할을 구분해야 했습니다.

• i: 정렬된 영역에 삽입할 원소의 최초 위치입니다
• j: 원소가 왼쪽으로 이동하면서 바뀌는 현재 위치입니다
• j - 1: 현재 원소의 바로 앞 위치입니다

i는 내부 반복에서 그대로 있는 것이 정상입니다. 실제 이동은 j가 담당해야 합니다.

def insertion_sort(array):
    n = len(array)

    for i in range(1, n):
        for j in range(i, 0, -1):
            if array[j - 1] > array[j]:
                array[j - 1], array[j] = array[j], array[j - 1]
            else:
                break

    return array

여기서 중요한 점은 현재 값이 한 번 교환되고 끝나는 게 아니라는 것입니다. 바로 앞의 값과 비교해서 앞의 값이 더 크면 교환하고, 그 앞의 값과 또 비교하는 과정을 반복합니다. 자기보다 작거나 같은 값을 만나는 순간 멈춥니다.

[5, 4, 9, 1, 3]을 처음부터 끝까지 따라가면 다음과 같습니다.

i = 3을 보면 1이 9, 5, 4와 차례로 비교하면서 한 칸씩 왼쪽으로 이동합니다. 왼쪽 영역은 이미 정렬되어 있기 때문에, 자기보다 작은 값을 만나면 그 앞은 더 볼 필요가 없습니다. i = 4에서 3이 1을 만나 break하는 순간이 바로 그 경우입니다.

Insertion Sort에서 break가 자연스러운 이유

Insertion Sort에서는 i보다 왼쪽 영역이 이미 정렬되어 있습니다. 현재 값보다 작거나 같은 값을 만나면 그보다 왼쪽의 값들도 더 작으므로 비교를 계속할 필요가 없습니다.

이미 정렬된 [1, 2, 3, 4, 5]에서는 각 i마다 바로 앞의 값과 한 번만 비교하고 종료합니다. 그래서 최선 시간 복잡도는 O(n)이 됩니다. 평균과 최악은 O(n²)입니다.

break 자체가 시간 복잡도를 줄이는 것은 아닙니다. 남은 비교가 불필요하다는 사실을 알고 있을 때 종료할 수 있는 것입니다.

세 정렬을 다시 비교하면

세 정렬은 모두 기본 정렬이고, 큰 입력에서는 보통 직접 구현해서 쓰기보다 언어에서 제공하는 정렬을 사용합니다. 그래도 직접 구현해보면 반복문 안에서 무슨 일이 일어나는지 확인할 수 있습니다.

제가 다시 정리하면서 기준으로 잡은 차이는 다음과 같습니다.

정리

이번 글은 정렬 알고리즘을 깊게 파고들기보다는, 문제를 풀 때 시간복잡도를 감으로만 보지 않기 위해 다시 정리한 글입니다.

• Bubble Sort는 이웃한 두 값을 비교하고 교환합니다
• Selection Sort는 남은 구간의 최솟값을 찾은 뒤 한 번 교환합니다
• Insertion Sort는 현재 값을 왼쪽의 정렬된 영역에 삽입합니다
• 세 정렬 모두 평균과 최악은 O(n²)입니다
• Bubble Sort는 한 바퀴 전체에서 교환이 없을 때 조기 종료할 수 있습니다
• Selection Sort는 교환이 없다는 사실만으로 뒤쪽 영역의 정렬을 보장할 수 없습니다
• Insertion Sort는 왼쪽 영역이 이미 정렬되어 있기 때문에 필요한 위치를 찾으면 멈출 수 있습니다