선택 정렬 알고리즘 원리, 코드, 시간 복잡도

쉬운 말로 설명하는 원리

리스트 전체를 훑어 가장 작은 요소를 찾습니다. 그것을 인덱스 0의 요소와 교환하면 이제 인덱스 0은 확정입니다. 인덱스 1부터 나머지를 훑어 가장 작은 요소를 찾아 인덱스 1과 교환합니다. 요소가 하나만 남을 때까지 계속하면, 남은 것은 가장 큰 요소입니다.

버블 정렬이나 삽입 정렬과 달리 선택 정렬은 입력이 이미 정렬되어 있어도 이득이 없습니다. 최솟값을 찾았다고 확신하려면 남은 요소를 모두 훑어야 하기 때문입니다.

단계별 예제

[64, 25, 12, 22, 11]을 정렬해 봅시다. 막대 앞 부분은 정렬이 끝나 확정된 부분입니다.

요소 5개에 4단계이며, 비교는 4 + 3 + 2 + 1 = 10번, 실제 교환은 3번입니다.

파이썬 구현

def selection_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]
    return items
print(selection_sort([64, 25, 12, 22, 11]))   # [11, 12, 22, 25, 64]
print(selection_sort([2, 1]))                 # [1, 2]

마지막 남은 요소는 자동으로 제자리에 있으므로 바깥 반복문은 n − 1번 실행됩니다. 안쪽 반복문은 인덱스만 기록하고, 교환은 바깥 단계마다 한 번만 일어납니다.

시간 복잡도와 공간 복잡도

쓰기 횟수가 적다는 점이 선택 정렬의 유일한 실질적 강점입니다. 일부 플래시 메모리처럼 메모리에 쓰는 비용이 읽는 비용보다 훨씬 크거나 큰 레코드를 옮겨야 할 때는 쓰기를 줄이는 것이 중요할 수 있습니다. 사이클 정렬(cycle sort)은 이를 더 밀어붙여 각 요소를 최대 한 번만 씁니다.

안정성: 선택 정렬이 안정 정렬이 아닌 이유

안정 정렬은 같은 값의 요소가 원래의 상대적 순서를 유지하는 정렬입니다. 선택 정렬은 멀리 떨어진 요소를 교환하므로, 같은 값을 가진 다른 요소를 뛰어넘을 수 있습니다.

def selection_sort_by_key(items, key):
    n = len(items)
    for i in range(n - 1):
        m = min(range(i, n), key=lambda j: key(items[j]))
        items[i], items[m] = items[m], items[i]
    return items
cards = [("4", "hearts"), ("4", "spades"), ("2", "clubs")]
print(selection_sort_by_key(cards, key=lambda c: c[0]))
# [('2', 'clubs'), ('4', 'spades'), ('4', 'hearts')]  order of the 4s changed

2가 하트 4와 교환되면서 하트 4가 스페이드 4 뒤로 옮겨졌습니다. 안정 버전도 있습니다. 교환하는 대신 최솟값을 빼내 위치 i에 끼워 넣고 나머지를 오른쪽으로 밀면 순서는 유지되지만 단계마다 쓰기가 O(n)번 듭니다.

선택 정렬과 다른 정렬 비교

힙 정렬은 더 나은 자료구조를 쓰는 선택 정렬입니다. 남은 요소 중 가장 큰 것을 반복해서 선택하는 점은 같지만, O(n) 탐색 대신 이진 힙으로 O(log n)에 찾으므로 전체가 O(n log n)이 됩니다.

선택 정렬을 쓰는 경우

실제 파이썬 코드에서는 내장 sorted()나 list.sort()를 쓰세요. 선택 정렬은 교육용 예제로, 제약이 있는 환경의 아주 작은 고정 크기 배열에, 쓰기 횟수를 최소화해야 할 때 알아 둘 가치가 있습니다. 시험과 면접에서 자주 나오며, 보통 단계를 추적하고, 비교와 교환 횟수를 세고, 안정 정렬이 아닌 이유를 설명하라는 형태입니다.