선택 정렬: 교환 횟수를 줄이는 제자리 정렬

선택 정렬은 남아 있는 구간을 매번 끝까지 훑어 가장 작은 값을 앞자리에 놓는다. 비교 횟수는 많지만 교환은 패스당 최대 한 번뿐이라, 메모리와 쓰기 비용이 제약인 환경에서는 선택할 이유가 분명하다.

남은 구간에서 최솟값을 고르는 방식

i번째 위치를 확정할 때마다 구간 i..n-1에서 최솟값의 인덱스를 찾고, 필요할 때만 해당 값을 i번째 요소와 교환한다. 이 과정을 왼쪽에서 오른쪽으로 반복하면 배열은 오름차순으로 정렬된다.

외부 보조 메모리를 쓰지 않는 제자리(in-place) 알고리즘이며, 비교 연산의 시간 복잡도는 O(n^2)이다. 교환은 최대 n−1회 발생한다. 입력 데이터의 분포와 무관하게 동작 패턴이 일정하다는 점도 특징이다.

기본 구현은 동일 키의 상대적 순서를 보장하지 않는 불안정 정렬이다. 상대 순서를 유지해야 한다면 안정 변형을 쓰거나 다른 알고리즘을 선택해야 한다.

정렬이 진행되는 흐름

⤢✕

배열 길이가 n보다 작으면 아무 작업도 하지 않는다. 그렇지 않으면 각 위치에서 최솟값을 찾고, 현재 위치와 최솟값 위치가 다를 때만 교환한다. 비교할 수 없는 타입이 섞인 데이터에는 적용할 수 없다.

양방향 선택(min-max) 변형은 한 패스에서 양쪽 끝을 함께 배치해 패스 수를 줄일 수 있다. 다만 비교 횟수는 여전히 Θ(n^2)이다. 거의 정렬된 입력이라도 일찍 끝내기(early exit)로 얻는 이점은 크지 않다.

Python으로 구현하기

가변 시퀀스인 list와 서로 비교 가능한 동형 요소를 전제로 한다. 아래 구현은 원본 배열을 직접 정렬한다.

def selection_sort(a):
    n = len(a)
    if n < 2:
        return a
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        if m != i:
            a[i], a[m] = a[m], a[i]
    return a

# 사용 예
data = [5, 2, 4, 2, 1]
selection_sort(data)
print(data)  # [1, 2, 2, 4, 5]

이 구현의 비교 비용은 O(n^2)이고 교환은 n−1회를 넘지 않는다. 동일한 값을 가진 요소의 순서는 바뀔 수 있다.

상대 순서를 보존하려면 스왑 대신 최솟값을 꺼낸 뒤, 그 사이의 요소를 한 칸씩 오른쪽으로 옮긴다.

def stable_selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        key = a[m]
        while m > i:
            a[m] = a[m - 1]
            m -= 1
        a[i] = key
    return a

안정성은 확보되지만 쓰기 횟수는 늘어난다. 비교 연산은 여전히 O(n^2)이다.

다른 단순 정렬과 비교할 때

알고리즘	성능(평균)	성능(최악)	공간	안정성	일관성(성능 변동성)	확장성(대용량)	운영 편의
선택 정렬	O(n^2)	O(n^2)	O(1)	불안정	높음	낮음	높음
삽입 정렬	O(n^2)	O(n^2)	O(1)	안정	중간(거의 정렬 시 개선)	낮음	높음
버블 정렬	O(n^2)	O(n^2)	O(1)	안정	중간	낮음	보통
퀵 정렬	O(n log n)	O(n^2)	O(log n)	불안정	낮음	높음	보통

선택 정렬은 상수 공간과 적은 교환 횟수를 얻는 대신 대용량 데이터에는 확장성이 낮다.

메모리와 쓰기 비용이 우선인 경우

임베디드나 마이크로컨트롤러처럼 메모리가 제한되고 실행 시간의 예측 가능성이 필요한 환경에서 사용할 수 있다. 인터럽트를 비활성화한 짧은 정렬 작업에도 맞으며, 단순한 분기와 캐시 패턴은 코드 크기와 검증 부담을 줄이는 데 도움이 된다.

플래시나 EEPROM처럼 쓰기 수명에 제약이 있는 매체에서도 교환 횟수가 최대 n−1회라는 특성이 유용하다. 기록 사이클을 줄이는 선택지가 될 수 있다.

레코드 수가 매우 작은 배치, 즉 n≲30 수준의 전처리에서는 외부 의존성 없이 간단히 적용할 수 있다. 테스트 벡터 정렬이나 회귀 테스트의 기준선 알고리즘으로도 쓸 수 있다. k가 매우 작고 n도 작다면 k회 패스를 수행해 O(k·n) 방식의 제한적 Top-k 선택을 구현할 수 있으며, 대규모 데이터에는 힙이나 선택 알고리즘(Quickselect)이 더 적합하다.

선택 전에 확인할 조건

선택 정렬은 추가 메모리를 0에 가깝게 쓰는 O(1) 공간 알고리즘이고, 교환 횟수는 최대 n−1회다. n≤30 수준에서는 단순 구현의 오버헤드를 최소화할 수 있다.

데이터셋이 매우 작거나 메모리와 쓰기 제한이 엄격할 때 우선 검토할 만하다. 반대로 평균과 최악 모두 O(n^2)이므로 대용량 처리나 높은 실시간 성능이 필요한 경우에는 적합하지 않다.

구현할 때는 min == i 검사를 통해 불필요한 교환을 피하고, 비교 함수를 분기 예측과 캐시에 친화적인 형태로 단순하게 유지한다. 테스트에는 역정렬, 중복 값이 많은 입력, 모든 값이 같은 입력 같은 경계 사례를 포함한다. 안정성이 요구되면 안정 변형 또는 다른 안정 정렬을 사용한다.