[Algorithm] 선택 정렬 (Selection Sort) 완벽 정리

선택 정렬(Selection Sort)은 가장 직관적인 정렬 알고리즘 중 하나다. 이름처럼 배열에서 최소값을 선택해 정렬되지 않은 부분의 맨 앞으로 옮긴다. 구현이 간단하고 동작 원리가 분명해서 알고리즘을 처음 배울 때 많이 쓴다.

이 글의 코드는 Python(파이썬)으로 먼저 보여 주고, 뒤에서 같은 것을 자바로 다시 짠다. 파이썬 문법은 자바와 다른 곳만 코드 바로 뒤에서 짚는다.

선택 정렬이란?

선택 정렬은 정렬되지 않은 부분에서 최소값을 찾아 맨 앞으로 옮기는 알고리즘이다. 배열을 앞쪽의 정렬된 부분과 뒤쪽의 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분에서 가장 작은 원소를 찾아 정렬된 부분의 끝에 붙인다. 처음에는 정렬된 부분이 비어 있으므로 배열 전체가 「정렬되지 않은 부분」이다.

동작 원리

정렬되지 않은 부분(처음에는 배열 전체)에서 최소값을 찾는다
그 최소값을 정렬되지 않은 부분의 맨 앞 원소와 맞바꾼다. 이제 그 자리는 정렬된 부분에 들어간다
정렬된 부분을 뺀 나머지에서 1~2를 반복한다
정렬되지 않은 부분에 원소가 하나만 남으면 끝난다. 남은 하나는 저절로 가장 큰 값이다

인터랙티브 애니메이션

위에서 설명한 선택 정렬 과정을 직접 눈으로 확인할 수 있다. 시작 버튼을 눌러 정렬 과정을 단계별로 본다.

속도:

느림 보통 빠름

배열을 정렬할 준비가 되었습니다.

비교 0

교환 0

패스 0

회색: 정렬되지 않은 기본 상태
노란색: 현재 최소값을 찾기 위해 비교 중인 요소
파란색: 현재까지 찾은 최소값
빨간색: 교환이 발생하는 요소 (위치 이동 애니메이션)
초록색: 정렬이 완료된 요소
속도를 조절해 천천히 또는 빠르게 볼 수 있다

코드 구현

뒤의 절들(안정성 · 최적화 · 실전 문제)이 이 기본 코드를 고친 모양으로 나오므로, 기본 코드를 먼저 본다.

Python 구현

기본 버전

def selection_sort(arr):
    """
    선택 정렬 기본 구현
    
    Args:
        arr (list): 정렬할 리스트
    
    Returns:
        list: 정렬된 리스트
    """
    n = len(arr)
    
    # 정렬되지 않은 부분에서 최소값 찾기
    for i in range(n - 1):
        min_idx = i  # 최소값의 인덱스
        
        # i+1부터 끝까지 최소값 찾기
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # 최소값을 현재 위치와 교환
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr


# 사용 예시
numbers = [5, 3, 8, 4, 2]
print(f"정렬 전: {numbers}")
selection_sort(numbers)
print(f"정렬 후: {numbers}")

한 줄씩 따라가기

def selection_sort(arr):는 arr를 매개변수로 받는 함수를 정의한다. 자바의 메서드 선언과 같은 역할인데, 매개변수와 반환값의 타입을 적지 않는다. 중괄호 { } 대신 콜론(:) 뒤의 들여쓰기가 몸통의 범위를 정한다 — 들여쓰기 칸 수가 같은 줄끼리 한 블록이고, 한 단계 줄어들면 그 블록이 끝난다
함수 바로 아래 따옴표 세 개(""")로 감싼 글은 독스트링이다. 자바의 /** */ 문서 주석과 같은 자리이고 실행에는 영향이 없다. 안의 Args: · Returns:는 매개변수와 반환값을 설명하는 관례적인 형식이다
#으로 시작하는 부분은 주석이다. 자바의 //와 같다
n = len(arr)의 len()은 리스트의 길이를 돌려준다. 자바의 arr.length와 같다
for i in range(n - 1):의 range(n - 1)은 0부터 n - 2까지 센다. 끝 값 n - 1은 들어가지 않는다. 그래서 이 줄은 자바의 for (int i = 0; i < n - 1; i++)과 같다. 마지막 원소 하나는 남은 것들 중 저절로 가장 크므로 n - 1번만 돈다
for j in range(i + 1, n):처럼 값을 두 개 주면 i + 1부터 n - 1까지 센다. 자바의 for (int j = i + 1; j < n; j++)이다. i번 자리 뒤쪽, 즉 정렬되지 않은 부분만 훑는다
arr[i], arr[min_idx] = arr[min_idx], arr[i]는 두 원소를 맞바꾸는 파이썬 문법이다. 자바라면 int temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp;처럼 임시 변수가 필요하지만, 파이썬은 =의 오른쪽 두 값을 먼저 한 쌍으로 묶어 계산한 다음 왼쪽 두 자리에 순서대로 나눠 넣기 때문에 임시 변수 없이 교환이 끝난다
selection_sort(numbers)는 반환값을 받지 않는데도 다음 줄에서 numbers가 정렬돼 있다. 파이썬 리스트는 자바 배열처럼 메서드에 넘기면 같은 리스트를 가리키므로, 함수 안에서 바꾼 것이 원본에 그대로 남는다. return arr는 sorted_list = selection_sort(numbers)처럼 받아 쓰고 싶을 때를 위한 것이고, 돌려주는 것도 같은 리스트다
print(f"정렬 전: {numbers}")의 f"..."는 f-string이다. 중괄호 { } 안의 변수 값이 그 자리에 끼워진다. 자바의 "정렬 전: " + numbers와 같은 역할이다

내림차순 버전

def selection_sort_descending(arr):
    """
    선택 정렬 내림차순 구현
    
    Args:
        arr (list): 정렬할 리스트
    
    Returns:
        list: 내림차순으로 정렬된 리스트
    """
    n = len(arr)
    
    for i in range(n - 1):
        max_idx = i  # 최대값의 인덱스
        
        # i+1부터 끝까지 최대값 찾기
        for j in range(i + 1, n):
            if arr[j] > arr[max_idx]:
                max_idx = j
        
        # 최대값을 현재 위치와 교환
        arr[i], arr[max_idx] = arr[max_idx], arr[i]
    
    return arr


# 사용 예시
numbers = [5, 3, 8, 4, 2]
print(f"정렬 전: {numbers}")
selection_sort_descending(numbers)
print(f"정렬 후 (내림차순): {numbers}")

한 줄씩 따라가기: 기본 버전과 달라진 곳은 if arr[j] > arr[max_idx]: 한 줄이다. <를 >로 바꿔 최소값 대신 최대값을 찾아 앞에 놓으므로, 큰 값부터 작은 값 순서(내림차순)가 된다. 변수 이름 min_idx를 max_idx로 바꾼 것은 뜻을 맞추려는 것일 뿐이다.

제네릭 버전 (비교 함수 사용)

def selection_sort_generic(arr, key=None, reverse=False):
    """
    제네릭 선택 정렬 구현
    
    Args:
        arr (list): 정렬할 리스트
        key (function): 비교 기준 함수
        reverse (bool): True면 내림차순, False면 오름차순
    
    Returns:
        list: 정렬된 리스트
    """
    n = len(arr)
    
    for i in range(n - 1):
        selected_idx = i
        
        for j in range(i + 1, n):
            # key 함수가 있으면 적용
            val_j = key(arr[j]) if key else arr[j]
            val_selected = key(arr[selected_idx]) if key else arr[selected_idx]
            
            # reverse에 따라 비교
            if reverse:
                if val_j > val_selected:
                    selected_idx = j
            else:
                if val_j < val_selected:
                    selected_idx = j
        
        arr[i], arr[selected_idx] = arr[selected_idx], arr[i]
    
    return arr


# 사용 예시
# 1. 문자열 길이로 정렬
words = ["apple", "pie", "banana", "cat"]
selection_sort_generic(words, key=len)
print(f"길이 순 정렬: {words}")

# 2. 튜플의 두 번째 요소로 정렬
data = [(1, 5), (3, 2), (2, 8), (4, 1)]
selection_sort_generic(data, key=lambda x: x[1])
print(f"두 번째 요소 순 정렬: {data}")

# 3. 절댓값으로 정렬
numbers = [-5, 3, -8, 4, -2]
selection_sort_generic(numbers, key=abs)
print(f"절댓값 순 정렬: {numbers}")

한 줄씩 따라가기

def selection_sort_generic(arr, key=None, reverse=False):의 key=None, reverse=False는 매개변수의 기본값이다. 호출할 때 그 값을 안 넘기면 key는 None(자바의 null), reverse는 False가 된다. 자바라면 매개변수 개수가 다른 메서드를 여러 개 만들어(오버로딩) 흉내 내는 것을 파이썬은 한 줄로 한다
key에는 숫자나 문자열이 아니라 함수를 넘긴다. 파이썬에서는 함수도 변수에 담아 다른 함수에 넘길 수 있다. 이 함수는 원소 하나를 받아 「무엇을 기준으로 비교할지」를 돌려준다
key(arr[j]) if key else arr[j]는 파이썬의 조건부 표현식이다. 「조건이 참일 때 값 if 조건 else 조건이 거짓일 때 값」 순서로 읽는다 — 자바의 삼항 연산자로 쓰면 key != null ? key(arr[j]) : arr[j]와 같은 뜻이다. key 함수가 전달됐으면 그 함수로 arr[j]를 가공한 값을 쓰고, 전달되지 않았으면 arr[j]를 그대로 쓴다
selection_sort_generic(words, key=len)처럼 호출할 때 이름=값으로 넘기면, 순서와 상관없이 그 이름의 매개변수에 값이 들어간다. reverse는 안 넘겼으니 기본값 False다. len 뒤에 괄호가 없는 것은 len을 지금 실행하지 않고 함수 자체를 넘긴다는 뜻이다. 그래서 정렬 안에서 key(arr[j])가 len(arr[j]), 즉 문자열 길이가 된다. key=abs도 같아서 절댓값(abs)으로 비교한다
data = [(1, 5), (3, 2), ...]의 (1, 5)는 값 두 개를 묶은 튜플이다. key=lambda x: x[1]의 lambda x: x[1]은 람다다 — x를 받아서 x[1](튜플의 두 번째 값)을 돌려주는 이름 없는 함수를 그 자리에서 만들어 key로 넘긴 것이다

Java 구현

기본 버전

public class SelectionSort {
    
    /**
     * 선택 정렬 기본 구현
     * 
     * @param arr 정렬할 배열
     */
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // 정렬되지 않은 부분에서 최소값 찾기
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;  // 최소값의 인덱스
            
            // i+1부터 끝까지 최소값 찾기
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            
            // 최소값을 현재 위치와 교환
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
    
    /**
     * 배열 출력
     */
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] numbers = {5, 3, 8, 4, 2};
        
        System.out.print("정렬 전: ");
        printArray(numbers);
        
        selectionSort(numbers);
        
        System.out.print("정렬 후: ");
        printArray(numbers);
    }
}

한 줄씩 따라가기: 파이썬 기본 버전과 한 줄씩 짝이 맞는다. range(n - 1)이 for (int i = 0; i < n - 1; i++)로, 한 줄 교환이 temp를 쓰는 세 줄로 바뀌었을 뿐이다. 반환 타입이 void인 것은 자바 배열도 넘긴 원본을 그대로 바꾸기 때문이다.

제네릭 버전

import java.util.Comparator;

public class SelectionSortGeneric {
    
    /**
     * 제네릭 선택 정렬 구현
     * 
     * @param arr 정렬할 배열
     * @param comparator 비교자 (null이면 자연 순서)
     */
    public static <T extends Comparable<T>> void selectionSort(
            T[] arr, Comparator<T> comparator) {
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            int selectedIdx = i;
            
            for (int j = i + 1; j < n; j++) {
                // Comparator가 있으면 사용, 없으면 자연 순서
                int cmp = (comparator != null) 
                    ? comparator.compare(arr[j], arr[selectedIdx])
                    : arr[j].compareTo(arr[selectedIdx]);
                
                if (cmp < 0) {
                    selectedIdx = j;
                }
            }
            
            // 교환
            T temp = arr[i];
            arr[i] = arr[selectedIdx];
            arr[selectedIdx] = temp;
        }
    }
    
    /**
     * 자연 순서로 정렬 (오름차순)
     */
    public static <T extends Comparable<T>> void selectionSort(T[] arr) {
        selectionSort(arr, null);
    }
    
    public static void main(String[] args) {
        // Integer 배열 정렬
        Integer[] numbers = {5, 3, 8, 4, 2};
        System.out.print("정렬 전: ");
        printArray(numbers);
        
        selectionSort(numbers);
        
        System.out.print("정렬 후: ");
        printArray(numbers);
        
        // 내림차순 정렬
        Integer[] numbers2 = {5, 3, 8, 4, 2};
        selectionSort(numbers2, Comparator.reverseOrder());
        
        System.out.print("내림차순: ");
        printArray(numbers2);
        
        // 문자열 길이로 정렬
        String[] words = {"apple", "pie", "banana", "cat"};
        selectionSort(words, Comparator.comparingInt(String::length));
        
        System.out.print("길이 순: ");
        printArray(words);
    }
    
    private static <T> void printArray(T[] arr) {
        for (T item : arr) {
            System.out.print(item + " ");
        }
        System.out.println();
    }
}

한 줄씩 따라가기

<T extends Comparable<T>>는 제네릭 타입 매개변수 T에 「Comparable을 구현한 타입만 올 수 있다」는 제한을 건 것이다. Integer · String은 이미 Comparable을 구현하고 있어서 T 자리에 들어갈 수 있고, 컴파일러는 T 타입끼리 compareTo()로 비교할 수 있다는 것을 미리 확인해 준다
Comparator<T> comparator는 비교 기준을 바깥에서 따로 넘기고 싶을 때 쓰는 매개변수다(Comparator). comparator가 null이면(비교 기준을 안 넘겼으면) arr[j].compareTo(arr[selectedIdx])로 타입 자신의 자연 순서를 쓰고, null이 아니면 comparator.compare(...)로 넘겨받은 기준을 쓴다
if (cmp < 0): compare(a, b)와 a.compareTo(b)는 둘 다 a가 앞이어야 하면 음수, b가 앞이어야 하면 양수, 같으면 0을 돌려준다고 약속돼 있다. 그래서 cmp < 0은 「arr[j]가 지금까지 고른 값보다 앞에 와야 한다」는 뜻이고, 기본 버전의 arr[j] < arr[minIdx]와 같은 자리다
인자 하나짜리 selectionSort(T[] arr)는 비교 기준 자리에 null을 넣어 두 인자짜리를 부른다. 이름이 같고 매개변수가 다른 메서드 두 개, 즉 오버로딩이다
main에서 int[]가 아니라 Integer[]를 쓰는 이유는 제네릭의 T 자리에 int 같은 기본 타입이 들어갈 수 없어서다. 그래서 int를 객체로 감싼 래퍼 클래스 Integer의 배열을 넘긴다. Integer[] numbers = {5, 3, 8, 4, 2};처럼 int 값을 그대로 적어도 컴파일되는 것은, 자바가 int 값을 Integer 객체로 알아서 감싸 주기 때문이다(오토박싱이라고 부른다)
Comparator.reverseOrder()는 자연 순서를 거꾸로 뒤집은 비교 기준을 돌려준다. int 5에는 메서드를 부를 수 없지만, Integer로 감싼 5와 3을 비교한 Integer.valueOf(5).compareTo(3)은 양수다. 이 기준에서는 그 결과가 음수가 되므로 이 기준에서는 음수가 되므로, 큰 값이 앞에 오는 내림차순이 된다
Comparator.comparingInt(String::length)는 「두 문자열을 각각 length()로 숫자로 바꾼 뒤 그 숫자를 비교하는」 비교 기준을 만들어 돌려준다. String::length는 메서드 참조다 — s -> s.length()와 같은 뜻이다. 파이썬 버전의 key=len과 같은 일을 한다

정렬 과정 시각화 버전

public class SelectionSortVisualized {
    
    /**
     * 선택 정렬 과정을 시각화하여 출력
     * 
     * @param arr 정렬할 배열
     */
    public static void selectionSortWithVisualization(int[] arr) {
        int n = arr.length;
        
        System.out.println("초기 상태:");
        printArrayWithHighlight(arr, -1, -1);
        System.out.println();
        
        for (int i = 0; i < n - 1; i++) {
            System.out.println("--- " + (i + 1) + "회차 ---");
            int minIdx = i;
            
            // 최소값 찾기
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            
            // 교환 전 상태
            System.out.println("최소값 찾음: arr[" + minIdx + "] = " + arr[minIdx]);
            
            // 교환
            if (minIdx != i) {
                System.out.println("교환: arr[" + i + "] ↔ arr[" + minIdx + "]");
                int temp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = temp;
            } else {
                System.out.println("교환 없음 (이미 최소값)");
            }
            
            // 교환 후 상태
            printArrayWithHighlight(arr, i, -1);
            System.out.println();
        }
        
        System.out.println("정렬 완료!");
        printArrayWithHighlight(arr, n - 1, -1);
    }
    
    /**
     * 배열을 출력하며 특정 위치를 강조
     */
    private static void printArrayWithHighlight(int[] arr, int sortedUntil, int current) {
        for (int i = 0; i < arr.length; i++) {
            if (i <= sortedUntil) {
                System.out.print("[" + arr[i] + "]");  // 정렬된 부분
            } else if (i == current) {
                System.out.print("(" + arr[i] + ")");  // 현재 비교 중
            } else {
                System.out.print(" " + arr[i] + " ");   // 정렬 안 된 부분
            }
            System.out.print(" ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] numbers = {5, 3, 8, 4, 2};
        selectionSortWithVisualization(numbers);
    }
}

한 줄씩 따라가기

printArrayWithHighlight(arr, sortedUntil, current)는 sortedUntil번 자리까지를 [ ]로, current번 자리를 ( )로 감싸 찍는다. 배열 번호는 0부터라서 -1은 「해당하는 자리가 없다」는 뜻이다. 그래서 처음의 printArrayWithHighlight(arr, -1, -1)은 정렬된 부분도, 비교 중인 자리도 없이 찍는다
회차마다 부르는 printArrayWithHighlight(arr, i, -1)은 0번부터 i번까지를 정렬된 부분으로 표시한다
current에는 이 예제에서 늘 -1만 넘기므로 ( )로 감싸는 분기는 실행되지 않는다. 비교 중인 자리까지 찍고 싶으면 안쪽 for 안에서 printArrayWithHighlight(arr, i - 1, j)처럼 불러 쓰라고 남겨 둔 자리로 보인다. 원래 의도는 확인하지 않았다

복잡도 분석

시간 복잡도

시간 복잡도는 입력 크기가 늘어날 때 연산 횟수가 얼마나 늘어나는지를 나타낸 것이고, 이를 적을 때 빅오 표기를 쓴다. 아래 표에서 최선은 가장 적게 걸리는 경우, 평균은 일반적인 경우, 최악은 가장 많이 걸리는 경우를 뜻한다.

경우	복잡도	설명
최선 (Best)	O(n²)	이미 정렬된 경우에도 모든 비교 수행
평균 (Average)	O(n²)	일반적인 경우
최악 (Worst)	O(n²)	어떤 입력이든 비교 횟수는 같다

선택 정렬은 최소값을 확인하려면 남은 원소를 전부 봐야 하므로, 입력이 이미 정렬돼 있든 거꾸로 돼 있든 비교 횟수가 똑같다. 그래서 세 경우가 모두 O(n²)이고, 최선과 최악 사이에 비교 횟수 차이가 없다. 다른 정렬 글에서 최악의 예로 드는 「역순으로 정렬된 경우」도 선택 정렬에서는 비교 횟수를 늘리지 않는다.

계산 과정

비교 횟수: (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2
교환 횟수: 최대 n-1번 (버블 정렬보다 적음)
따라서 시간 복잡도는 O(n²)

비교 횟수는 이렇게 나온다. 첫 회차는 0번 자리를 정하려고 뒤의 n-1개와 비교하고, 다음 회차는 n-2개, … 마지막 회차는 1개와 비교한다. 이 합을 구하려면 같은 합을 거꾸로 한 번 더 써서 위아래로 더한다.

  (n-1) + (n-2) + ... +   2   +   1
+   1   +   2   + ... + (n-2) + (n-1)
= n     + n     + ... + n     + n      ← n이 (n-1)개

위아래 짝마다 합이 n이고 짝이 n-1개이므로 두 번 더한 값은 n(n-1)이다. 한 번만 더한 값은 그 절반인 n(n-1)/2다. n=5면 4+3+2+1=10이고 5×4/2=10으로 맞는다.

n(n-1)/2를 풀면 n²/2 - n/2다. 빅오 표기는 n이 아주 커질 때 「얼마나 빨리 커지는가」만 보므로, 가장 빨리 커지는 항(n²/2)만 남기고 앞에 곱한 수(1/2)도 버린다. n이 1,000이면 n²/2는 500,000이고 n/2는 500이라 뒤의 항은 거의 차이를 못 낸다. 그래서 O(n²)이라고 부른다.

교환은 회차마다 한 번이고 회차가 n-1번이라 최대 n-1번이다. 버블 정렬(용어)은 바로 옆 두 원소를 비교해 순서가 거꾸로면 그 자리에서 맞바꾸는 정렬이라, 비교할 때마다 교환이 일어날 수 있다. 버블 정렬과의 차이는 아래 「버블 정렬과의 비교」에서 다시 본다.

특징: 선택 정렬은 데이터의 처음 상태와 관계없이 항상 O(n²)의 비교 연산을 한다.

공간 복잡도

O(1): 제자리 정렬(in-place sorting)
추가 메모리를 거의 사용하지 않음 (교환용 임시 변수만 필요)

장단점

장점

구현이 매우 간단하다: 코드가 직관적이고 이해하기 쉽다
추가 메모리가 거의 필요 없다: 공간 복잡도 O(1)
교환 횟수가 적다: 최대 n-1번의 교환만 일어난다 (비용이 큰 교환 연산에 유리)
작은 데이터에 쓸 만하다: 데이터가 적을 때는 구현이 간단해서 유용하다
데이터 이동 비용이 클 때 유리하다: 교환 횟수가 적어 데이터 이동이 비싼 경우 맞는다

교환 한 번은 메모리의 두 자리에 값을 새로 쓰는 일이다. 원소가 정수 하나면 싸지만, 원소 하나가 큰 덩어리라 통째로 옮겨야 하거나, 쓰기 자체가 느리고 쓸수록 닳는 저장 장치(플래시 메모리)에 직접 쓰는 경우라면 비싸진다. 3번과 5번이 말하는 「교환 · 이동 비용이 클 때」가 이런 경우다.

단점

느리다: 시간 복잡도 O(n²)라 대용량 데이터에 맞지 않는다
불안정 정렬(Unstable Sort): 같은 값의 순서가 보장되지 않는다
최선의 경우에도 O(n²): 이미 정렬된 배열도 모든 비교를 한다
실무에서 사용하지 않는다: 더 빠른 알고리즘을 쓴다

버블 정렬과의 비교

선택 정렬과 버블 정렬은 모두 O(n²) 알고리즘이지만 중요한 차이가 있다. 버블 정렬은 배열을 앞에서부터 훑으며 바로 옆 두 원소를 비교하고, 순서가 거꾸로면 그 자리에서 맞바꾼다. 한 바퀴를 돌면 가장 큰 값이 맨 뒤로 밀려나고, 이것을 반복한다.

특성	선택 정렬	버블 정렬
비교 방식	최소값을 찾아 교환	인접한 원소를 비교하여 교환
교환 횟수	최대 n-1번	최대 n(n-1)/2번
안정성	불안정 정렬	안정 정렬
최선의 경우	O(n²)	O(n) (최적화 시)
실제 성능	일반적으로 버블 정렬보다 빠름	교환이 많아 느림

버블 정렬의 교환 횟수 n(n-1)/2: 버블 정렬은 옆 두 원소만 맞바꾸므로, 교환 한 번에 「순서가 거꾸로 된 두 원소 쌍」이 정확히 하나 줄어든다. 배열이 완전히 역순이면 모든 쌍이 거꾸로라 쌍의 수만큼, 즉 n(n-1)/2번 교환해야 한다. 쌍의 수는 0번 원소가 뒤의 n-1개와, 1번 원소가 뒤의 n-2개와, … 마지막 바로 앞 원소가 맨 뒤 1개와 짝을 지어 (n-1) + (n-2) + … + 1개이고, 위 「계산 과정」에서 구한 대로 n(n-1)/2다
버블 정렬의 최선 O(n) 최적화: 한 바퀴를 도는 동안 교환이 한 번도 없었다면 이미 정렬된 것이므로 거기서 멈춘다. 이미 정렬된 배열이면 한 바퀴(n-1번 비교)만에 끝나서 O(n)이다. 자세한 코드는 버블 정렬 글에 있다
실제 성능: 비교 횟수는 둘 다 n(n-1)/2 정도인데 교환 횟수가 n-1 대 n(n-1)/2로 크게 차이 나서, 표는 선택 정렬이 보통 더 빠르다고 적었다. 나는 두 정렬의 실행 시간을 직접 재지는 않았다

언제 선택 정렬이 더 나을까?

교환 연산의 비용이 비교 연산보다 훨씬 클 때
메모리 쓰기 작업이 비쌀 때 (예: 플래시 메모리)
코드 단순성이 최우선일 때

안정성 문제

선택 정렬은 불안정 정렬이다. 같은 값을 가진 원소들의 상대적 순서가 유지되지 않는다. 아래는 그 예를 주석으로 적은 것이다(파이썬에서도 # 뒤는 주석이다).

# 예시: [4a, 2, 4b, 1] 정렬
# a, b는 같은 값이지만 구분을 위한 표시

# 1단계: 최소값 1을 찾아 맨 앞과 교환
# [1, 2, 4b, 4a]  <- 4a와 1이 교환되면서 4a와 4b의 순서가 바뀜

# 결과: [1, 2, 4b, 4a] 
# 원래 순서(4a -> 4b)가 바뀜 (4b -> 4a)

맨 앞의 4a가 멀리 떨어진 1과 자리를 바꾸면서 4b를 뛰어넘어 뒤로 간다. 이렇게 멀리 건너뛰는 교환 때문에 같은 값끼리의 순서가 뒤집힌다. 그 뒤의 회차는 순서를 되돌리지 않는다. 2회차는 남은 [2, 4b, 4a]에서 최소값 2가 이미 제자리라 그대로 두고, 3회차는 [4b, 4a]를 비교하는데 4a < 4b가 거짓(값이 같다)이라 최소값이 4b로 남아 교환하지 않는다. 그래서 결과가 [1, 2, 4b, 4a]다.

안정성이 필요한 경우에는 삽입 정렬(용어)이나 병합 정렬을 쓴다. 둘 다 같은 값끼리 순서를 바꾸지 않는 안정 정렬이다.

최적화 기법

1. 양방향 선택 정렬

한 번 훑을 때 최소값과 최대값을 동시에 찾아, 최소값은 왼쪽 끝에, 최대값은 오른쪽 끝에 놓는다. 기본 버전은 한 바퀴에 한 자리를 정하는데, 이 버전은 양쪽 끝 두 자리를 정한다.

def bidirectional_selection_sort(arr):
    """
    양방향 선택 정렬
    최소값과 최대값을 동시에 찾아 배치
    """
    left = 0
    right = len(arr) - 1
    
    while left < right:
        min_idx = left
        max_idx = right
        
        # 최소값과 최대값을 동시에 찾기
        for i in range(left, right + 1):
            if arr[i] < arr[min_idx]:
                min_idx = i
            if arr[i] > arr[max_idx]:
                max_idx = i
        
        # 최소값을 왼쪽 끝으로
        arr[left], arr[min_idx] = arr[min_idx], arr[left]
        
        # 최대값이 left에 있었다면 min_idx로 이동했으므로 조정
        if max_idx == left:
            max_idx = min_idx
        
        # 최대값을 오른쪽 끝으로
        arr[right], arr[max_idx] = arr[max_idx], arr[right]
        
        left += 1
        right -= 1
    
    return arr

한 줄씩 따라가기

left와 right는 아직 정렬되지 않은 구간의 왼쪽 끝과 오른쪽 끝 번호다. right = len(arr) - 1은 마지막 원소의 번호다
while left < right:는 구간에 원소가 두 개 이상 남아 있는 동안 돈다. 몸통은 들여쓰기로 정해진다
for i in range(left, right + 1):는 left부터 right까지 센다. range는 끝 값을 넣지 않으므로 right까지 포함하려고 + 1을 붙였다. 자바의 for (int i = left; i <= right; i++)이다
최소값을 왼쪽 끝과 맞바꾼 뒤의 if max_idx == left:가 이 코드에서 가장 헷갈리는 곳이다. 예로 [9, 1, 5]를 보면 처음 최소값은 1번 자리(1), 최대값은 0번 자리(9)다. 최소값 교환으로 [1, 9, 5]가 되면서 9는 0번에서 1번 자리, 즉 원래 최소값이 있던 min_idx로 옮겨 간다. max_idx가 아직 0번을 가리키면 엉뚱하게 1을 오른쪽 끝으로 보내므로, max_idx = min_idx로 바뀐 자리를 따라간다. 그다음 오른쪽 끝과 맞바꾸면 [1, 5, 9]가 된다
left += 1과 right -= 1로 정해진 양쪽 끝 두 자리를 구간에서 뺀다

이 최적화로 줄어드는 것은 바깥 반복 횟수다. 한 바퀴에 두 자리를 정하므로 바깥 while은 기본 버전의 절반쯤만 돈다. 대신 한 바퀴 안에서 원소마다 비교를 두 번(최소, 최대) 하므로 비교 횟수는 거의 같고, 한 바퀴에 교환을 두 번 하므로 교환 횟수도 거의 같다. 나는 무작위 정수 1,000개로 세어 봤다. 기본 버전은 비교 499,500번 · 교환 999번 · 바깥 반복 999번이었고, 양방향 버전은 비교 501,000번 · 교환 1,000번 · 바깥 반복 500번이었다.

바깥 반복이 절반이 되면 while의 조건 검사와 min_idx · max_idx를 새로 잡는 준비 일이 절반으로 준다. 시간의 대부분을 차지하는 비교는 그대로라 크게 빨라질 이유는 보이지 않는다. 실행 시간은 재지 않았다. 그래서 이 글이 「최적화」라고 부르는 것이 실제로 얼마나 빠른지는 확인하지 않은 채로 둔다.

이 글은 원래 「비교 횟수는 동일하지만 교환 횟수를 절반으로 줄일 수 있다」고 적었는데, 위처럼 세어 보니 절반이 되는 것은 교환 횟수가 아니라 바깥 반복 횟수였다. 그래서 고쳤다.

2. 힙 선택 정렬

선택 정렬은 매 회차 남은 원소를 전부 훑어 최소값을 찾는다. 이 「최소값 찾기」를 힙 자료구조에 맡기면 힙 정렬(Heap Sort)이 된다. 힙은 값들을 위아래로 갈라지는 트리 모양으로 늘어놓아, 맨 위에 늘 가장 작은(또는 가장 큰) 값이 오게 하는 자료구조다. 그래서 최소값을 전부 훑지 않고 맨 위에서 바로 꺼낼 수 있고, 꺼낸 뒤 다시 정리할 때는 맨 위에서 맨 아래까지 한 줄로 내려가며 자리를 바꾸면 되는데, 힙은 층마다 원소가 1개, 2개, 4개, 8개…로 두 배씩 늘어나는 모양이라 원소가 n개면 층 수가 약 log₂ n이다(1,000개면 10층). 그래서 다시 정리하는 데 O(log n)이 든다. 이것을 n번 하므로 전체가 O(n log n)이다.

언제 사용해야 할까?

적합한 경우

데이터가 매우 작을 때 (10~20개 이하)
교환 연산이 비교 연산보다 훨씬 비쌀 때
메모리 쓰기가 제한적인 환경 (플래시 메모리 등)
코드의 단순성이 최우선일 때
알고리즘 학습 목적

부적합한 경우

대용량 데이터 (100개 이상)
안정 정렬이 필요한 경우
성능이 중요한 실무 프로젝트
이미 정렬된 데이터 (최적화 불가)

여기 적은 「10~20개 이하」와 「100개 이상」은 어림값이다. 어디서 나온 숫자인지는 확인하지 않았고, 직접 재지도 않았다.

마지막 줄의 「최적화 불가」는 이런 뜻이다. 버블 정렬과 삽입 정렬은 이미 정렬된 배열이면 일찍 끝나서 O(n)에 가까워지지만, 선택 정렬은 정렬돼 있어도 최소값을 확인하려고 남은 원소를 전부 비교한다. 그래서 이미 정렬된 데이터라면 그 이점을 살리는 다른 정렬이 낫다.

다른 정렬 알고리즘과 비교

알고리즘	최선	평균	최악	공간	안정성	교환 횟수
선택 정렬	O(n²)	O(n²)	O(n²)	O(1)	불안정	O(n)
버블 정렬	O(n)	O(n²)	O(n²)	O(1)	안정	O(n²)
삽입 정렬	O(n)	O(n²)	O(n²)	O(1)	안정	O(n²)
퀵 정렬	O(n log n)	O(n log n)	O(n²)	O(log n)	불안정	O(n log n)
병합 정렬	O(n log n)	O(n log n)	O(n log n)	O(n)	안정	O(n log n)
힙 정렬	O(n log n)	O(n log n)	O(n log n)	O(1)	불안정	O(n log n)

각 정렬이 어떻게 움직이는지는 버블 정렬 · 삽입 정렬 · 퀵 정렬 글과 병합 정렬 · 힙 정렬 용어 페이지에 있다. 공간 칸에서 퀵 정렬의 O(log n)은 배열을 나눠 가며 자기 자신을 다시 부르는(재귀) 호출이 쌓이는 몫이다. 메서드를 부르면 그 호출이 끝날 때까지 지역 변수 등을 담은 기록 한 칸이 메모리(스택)에 쌓여 있다. 퀵 정렬은 평균적으로 배열을 반씩 나눠 들어가므로 반으로 나누는 횟수, 즉 log n 단계쯤 호출이 겹쳐 쌓이고, 그만큼 메모리를 쓴다. 그리고 병합 정렬의 O(n)은 두 조각을 합칠 때 쓰는 원소 수만큼의 임시 배열 몫이다.

선택 정렬의 장점: 교환 횟수가 가장 적다 (최대 n-1번)

실전 문제 연습

선택 정렬은 코딩 테스트에서 직접 구현하거나 원리를 응용하는 문제로 나온다.

예제 문제

정렬 과정 출력하기: 선택 정렬의 각 단계를 출력하는 프로그램 작성
K번째 선택 결과: K번 선택 후 배열의 상태 출력
최소 교환 횟수: 선택 정렬이 필요로 하는 교환 횟수 계산
K번째 작은 수 찾기: 선택 정렬의 원리를 이용하여 K번째 작은 수 찾기

아래는 1번과 4번을 기본 버전에서 조금 고친 코드다.

def selection_sort_with_steps(arr):
    """정렬 과정을 출력하는 선택 정렬"""
    n = len(arr)
    print(f"초기 상태: {arr}")
    
    for i in range(n - 1):
        min_idx = i
        
        # 최소값 찾기
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # 교환이 필요한 경우
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
            print(f"{i + 1}회차: 인덱스 {i}와 {min_idx} 교환 -> {arr}")
        else:
            print(f"{i + 1}회차: 교환 없음 (이미 최소값) -> {arr}")
    
    return arr


def find_kth_smallest(arr, k):
    """
    선택 정렬의 원리를 이용한 K번째 작은 수 찾기
    (완전히 정렬할 필요 없이 K번만 수행)
    """
    n = len(arr)
    
    for i in range(k):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr[k - 1]


# 실행 예시
numbers = [5, 3, 8, 4, 2]
print("=== 정렬 과정 ===")
selection_sort_with_steps(numbers.copy())

print("\n=== K번째 작은 수 찾기 ===")
numbers2 = [5, 3, 8, 4, 2, 9, 1]
k = 3
result = find_kth_smallest(numbers2.copy(), k)
print(f"{k}번째 작은 수: {result}")

한 줄씩 따라가기

selection_sort_with_steps는 기본 버전에 print 두 군데를 더했다. if min_idx != i:로 최소값이 이미 제자리에 있으면 교환을 건너뛰고 「교환 없음」을 찍는다. f"{i + 1}회차..."처럼 f-string의 중괄호 안에 계산식을 넣으면 그 결과값이 들어간다. 사람에게 보여 줄 회차는 1부터 세려고 i + 1을 썼다
find_kth_smallest는 바깥 반복을 range(n - 1) 대신 range(k)로, 즉 k번만 돈다. 선택 정렬은 한 회차에 가장 작은 값부터 하나씩 앞에 확정하므로, k번 돌면 앞의 k자리에 작은 값 k개가 순서대로 놓인다. k번째 작은 수는 그중 마지막인 arr[k - 1]이다(번호가 0부터라서 - 1). 예시의 [5, 3, 8, 4, 2, 9, 1]에서 k=3이면 3이 나온다
numbers.copy()는 리스트를 하나 새로 복사해 넘긴다. 함수가 넘겨받은 리스트를 직접 바꾸므로(기본 버전의 설명 참고), 원본 numbers를 그대로 남겨 두려고 사본을 넘긴 것이다

마무리

선택 정렬은 직관적이고 구현이 간단한 정렬 알고리즘이다. 실무에서는 거의 쓰지 않지만, 알고리즘의 기본 개념을 이해하는 데 쓸모가 있다.

핵심 요약

최소값을 선택하여 맨 앞으로 옮기는 직관적인 알고리즘
시간 복잡도는 모든 경우 O(n²), 공간 복잡도는 O(1)
불안정 정렬이지만 교환 횟수가 적음 (최대 n-1번)
교환이 훨씬 적어서 보통 버블 정렬보다 빠르다고 알려져 있다 (실행 시간은 직접 재지 않았다)
교환 비용이 비쌀 때 유리

선택 정렬을 이해했다면 다음 단계로 이것들을 공부하길 권한다.

삽입 정렬(Insertion Sort): 부분적으로 정렬된 데이터에 효율적
힙 정렬(Heap Sort): 선택 정렬의 발전형으로 O(n log n)
퀵 정렬(Quick Sort): 실무에서 가장 많이 사용되는 O(n log n) 알고리즘

참고 자료

위키백과 - 선택 정렬
VisuAlgo - 정렬 시각화
Introduction to Algorithms (CLRS — 저자 Cormen · Leiserson · Rivest · Stein 네 사람의 머리글자로 부르는 알고리즘 교과서)
GeeksforGeeks - Selection Sort

자신만의 철학을 만들어가는 중입니다.

최상단으로 이동했습니다!

Twitter Facebook LinkedIn

[Algorithm] 선택 정렬 (Selection Sort) 완벽 정리

선택 정렬이란?

동작 원리

인터랙티브 애니메이션

코드 구현

Python 구현

기본 버전

내림차순 버전

제네릭 버전 (비교 함수 사용)

Java 구현

기본 버전

제네릭 버전

정렬 과정 시각화 버전

복잡도 분석

시간 복잡도

계산 과정

공간 복잡도

장단점

장점

단점

버블 정렬과의 비교

안정성 문제

최적화 기법

1. 양방향 선택 정렬

2. 힙 선택 정렬

언제 사용해야 할까?

적합한 경우

부적합한 경우

다른 정렬 알고리즘과 비교

실전 문제 연습

예제 문제

마무리

핵심 요약

참고 자료

공유하기

댓글남기기

다른 포스트

[Proof] PostgreSQL timestamptz(6)는 세션 시간대가 달라도 같은 순간을 돌려주는가 — 지지

[Proof] PostgreSQL 기본 격리 수준에서 낙관락 catch가 동작하는가 — 지지

[OS] Windows 프로세스와 메모리 점검: 무엇이 메모리를 먹고 있나

[Javascript] MVVM: 화면과 값을 묶어 두면 무엇이 편해지고 무엇이 어려워지는가

목차