선택정렬의 비교 비용과 스왑 최소화 특성

최소값을 골라 정렬 구간을 넓히는 방식

선택정렬은 아직 정렬하지 않은 구간에서 최소값을 찾고, 이를 정렬이 끝난 구간의 다음 자리로 옮기는 비교 기반 알고리즘이다. k번째 단계에서는 인덱스 [k..n-1]에서 최소값의 위치를 찾은 뒤 A[k]와 교환한다. 이 과정을 거치면 정렬 완료 구간은 [0..k]까지 늘어난다.

루프가 시작될 때마다 [0..k-1]은 오름차순으로 정렬되어 있으며, 배열 전체에서 가장 작은 k개 원소를 포함한다는 불변식을 유지한다.

비교 횟수는 약 n(n-1)/2이므로 최선·평균·최악 모두 O(n^2)이다. 반면 교환은 최대 n-1회, 즉 O(n)에 그친다. 별도 버퍼 없이 동작하는 제자리(in-place) 정렬이며 추가 메모리는 O(1)이다.

기본적인 스왑 방식은 안정 정렬이 아니다. 최소값을 교환하지 않고 꺼낸 뒤 그 사이의 원소를 한 칸씩 시프트하면 상대적 순서를 유지할 수 있지만, 쓰기 비용은 O(n^2)로 늘어난다.

반복 과정

입력은 길이 n의 배열 A이며, 여기서는 오름차순을 기준으로 한다. 외부 루프는 k=0..n-2를 순회하고, 내부 루프가 현재 미정렬 구간의 최소값 인덱스를 찾는다. 최소값이 이미 k 위치에 있지 않을 때만 교환하면 된다.

n≤1이면 바로 종료한다. 구현할 때는 탐색 범위 [k..n-1]를 벗어나지 않도록 하고 배열 포인터의 유효성도 확인해야 한다.

⤢✕

C99 구현에서 확인할 부분

기본 구현은 스왑을 이용하므로 불안정하지만, 추가 공간을 사용하지 않고 최소값을 선택하는 흐름을 그대로 보여준다. 전제조건은 C99 이상, 정수 비교, 오름차순 정렬이다. 컴파일은 gcc -std=c99 -O2 sel.c -o sel로 할 수 있다.

#include <stddef.h>

void selection_sort(int a[], size_t n) {
    if (!a || n < 2) return;
    for (size_t k = 0; k + 1 < n; ++k) {
        size_t min_idx = k;
        for (size_t t = k + 1; t < n; ++t) {
            if (a[t] < a[min_idx]) min_idx = t;
        }
        if (min_idx != k) {
            int tmp = a[k];
            a[k] = a[min_idx];
            a[min_idx] = tmp;
        }
    }
}

동일한 최소값 탐색을 사용하되, 최소값을 꺼내고 [k..min_idx-1] 구간을 오른쪽으로 한 칸 옮기면 안정성을 보장할 수 있다.

#include <stddef.h>

void selection_sort_stable(int a[], size_t n) {
    if (!a || n < 2) return;
    for (size_t k = 0; k + 1 < n; ++k) {
        size_t min_idx = k;
        for (size_t t = k + 1; t < n; ++t) {
            if (a[t] < a[min_idx]) min_idx = t;
        }
        int key = a[min_idx];
        for (size_t t = min_idx; t > k; --t) a[t] = a[t - 1];
        a[k] = key;
    }
}

함수형 구현에서는 MAX 같은 상수 대신 인자 n을 루프 상한으로 사용해야 한다. 외부 루프는 k < n-1, 내부 루프는 t < n 조건을 사용하며, if(min > item[t])의 괄호를 정확히 닫아야 한다. 최소값 위치가 현재 위치와 다를 때만 스왑하는 조건도 필요하다.

void SelectionSort(int item[], int n){
    int min, min_index, k, t;
    if (!item || n < 2) return;
    for (k = 0; k < n - 1; k++) {
        min = item[k]; min_index = k;
        for (t = k + 1; t < n; t++) {
            if (min > item[t]) {
                min = item[t];  min_index = t;
            }
        }
        if (min_index != k) { // 불필요 스왑 방지
            item[min_index] = item[k];
            item[k] = min;
        }
    }
}

쓰기 비용이 제약인 상황

선택정렬은 비교 횟수가 많아 대규모 데이터에 적합하지 않다. 다만 스왑이 최대 n-1회라는 성질은 쓰기 비용이 큰 임베디드·플래시 저장장치 환경에서 의미가 있다.

소규모 데이터 처리에서도 구현의 간결성과 예측 가능한 수행 패턴을 활용할 수 있다. n ≤ 수백 수준의 데이터와 메모리 제한 환경에서는 상수 공간 사용이 장점이 된다. 알고리즘 교육에서는 루프 불변식, 선택과 교환의 관계, 다른 O(n^2) 정렬과의 성능 비교를 설명하기 좋다.

추가 메모리는 0(상수 공간)이고 스왑은 최대 n-1회이므로 메모리 사용량과 쓰기 연산을 줄일 수 있다. 구현과 검증이 단순하며 수행 패턴이 일정해 실시간성 분석에도 활용하기 쉽다.

삽입정렬·버블정렬과 비교

알고리즘	최선/평균/최악 시간	비교 횟수(근사)	스왑/쓰기 횟수	안정성	적응성(부분 정렬 시)	추가 공간
선택정렬	O(n^2)/O(n^2)/O(n^2)	~ n(n-1)/2	≤ n-1 스왑	불안정(기본)	낮음	O(1)
삽입정렬	O(n)/O(n^2)/O(n^2)	데이터 의존	이동 다수	안정	높음	O(1)
버블정렬	O(n)/O(n^2)/O(n^2)	~ n(n-1)/2	최대 O(n^2) 스왑	안정	중간	O(1)

선택정렬의 핵심 교환 조건은 비교는 많지만 스왑은 적다는 점이다. 부분적으로 정렬된 데이터에서는 삽입정렬이 유리하고, 최적화하지 않은 버블정렬은 스왑이 과도해질 수 있다. 데이터 규모가 작거나 쓰기 비용이 큰 환경, 또는 학습과 검증 목적에서 선택적으로 사용할 수 있으며 안정성이 필요하면 시프트 기반 변형을 적용한다.