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

정렬은 같은 원소들을 정해진 순서로 다시 놓는 문제입니다. 목표는 코드의 두 반복을 외우기보다, 한 차례가 끝나면 어느 구간이 확정되는지 설명하는 것입니다. 리스트 교환·반복·O 표기를 복습하세요.

개념과 약속

입력은 비교 가능한 숫자 목록, 출력은 오름차순 새 목록입니다. 버블 정렬은 왼쪽에서 오른쪽으로 이웃을 비교해 큰 값을 오른쪽으로 보냅니다. 한 차례가 끝나면 남은 구간의 최댓값이 오른쪽 끝에 확정됩니다. 선택 정렬은 남은 구간에서 최솟값 위치를 찾고 왼쪽 경계와 교환합니다. 확정되는 쪽이 반대입니다.

안정 정렬은 같은 정렬 키를 가진 항목들의 원래 상대 순서를 보존합니다. 버블의 > 비교는 같은 값끼리 교환하지 않아 안정적입니다. 선택 정렬은 먼 위치의 두 항목을 바꾸므로 일반적으로 안정적이지 않습니다. 숫자만 출력하면 동률 항목의 원래 신원을 볼 수 없으니 2A,2B처럼 이름을 붙여 손으로 확인합니다.

손으로 상태 추적하기

선택 정렬은 이미 정렬된 상태라도 남은 최솟값을 찾기 위한 비교를 계속합니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

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
        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([]))

실행 결과:

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

왜 맞고 언제 끝나는가

버블은 이웃 교환마다 지금까지 본 최댓값을 오른쪽으로 옮깁니다. 오른쪽 확정 구간은 다음 차례에서 건드리지 않습니다. 선택은 현재 최솟값을 왼쪽 경계에 넣어 왼쪽 확정 구간을 하나씩 늘립니다. 두 방법 모두 교환으로 원소 집합을 보존하고, 유한한 범위의 두 반복이 끝나면 정렬된 순서가 됩니다.

비용과 적용 범위

최악 시간은 둘 다 Θ(n²)입니다. 여기의 버블은 교환이 없는 차례에 멈추어 정렬된 입력에서 Θ(n)입니다. 선택은 입력 순서와 관계없이 Θ(n²) 비교입니다. 작업 목록 내부의 보조 변수는 O(1)이지만 이 교재의 함수는 원본 보존용 O(n) 복사를 포함합니다.

스스로 풀어 보기

1. 선택 정렬로 [2A,2B,1]을 숫자 키에 따라 정렬할 때 동률 A·B의 순서는 어떻게 바뀌나요?
2. 버블의 >를 >=로 바꾸면 안정성과 조기 종료에 어떤 영향이 있나요?

힌트

1. 첫 최솟값 1과 첫 항목 2A를 교환합니다.
2. 같은 값끼리도 교환했다고 기록합니다.

해설

1. [1,2B,2A]가 되어 상대 순서가 뒤집힙니다.
2. 같은 키끼리 뒤집을 수 있어 안정성이 깨집니다. 모두 같은 값인 입력에서도 교환이 있다고 기록되어 조기 종료의 이득이 사라집니다.

흔한 오해

선택 정렬이 교환을 적게 한다고 비교도 적은 것은 아닙니다. 비교 횟수·교환 횟수·복사 비용을 각각 구분하세요.

복습과 다음 연결

삽입 정렬은 왼쪽 구간을 정렬해 유지하는 다른 방법입니다. 결과 비교는 정렬 실험에서 이어갑니다.