선택 정렬 (Selection Sort)

선택 정렬은 맨 앞 자리부터 차례로, 그 자리에 들어갈 가장 작은 값을 골라(선택해) 넣는 정렬입니다.

한눈에 보기

• 거품 정렬과 비슷한 알고리즘으로, 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 방식입니다.
• 선택 정렬과 삽입 정렬을 헷갈리는 경우가 많습니다. 선택 정렬은 자리를 먼저 고르고, 그 자리에 올 값을 찾는 것이라고 기억하면 편합니다.
• 비유: 달리기 시상식에서 1등 자리에 설 사람을 전체에서 찾아 세우고, 2등 자리에 설 사람을 나머지에서 찾아 세우는 식입니다.
• 분류로 보면 비교 정렬, 같은 값의 순서가 바뀔 수 있는 불안정 정렬, 배열 안에서 자리만 바꾸는 제자리 정렬입니다.

동작 과정

오름차순 정렬 기준입니다.

1. 주어진 배열에서 최솟값을 찾습니다.
2. 그 값을 맨 앞에 있는 값과 교체합니다. (이 한 번을 한 회전, pass라고 부릅니다.)
3. 맨 처음 자리를 뺀 나머지 배열에 같은 방법을 반복합니다.

예시 배열 [4, 2, 5, 1]로 따라가 보겠습니다.

회전	채울 자리	찾은 최솟값	배열 상태	설명
시작	-	-	[4, 2, 5, 1]	처음 상태
1회전	0번	1 (3번 자리)	[1, 2, 5, 4]	4와 1을 교환
2회전	1번	2 (1번 자리)	[1, 2, 5, 4]	이미 제자리라 자기 자신과 교환
3회전	2번	4 (3번 자리)	[1, 2, 4, 5]	5와 4를 교환. 정렬 완료

마지막 한 자리는 남은 값이 하나뿐이라 따로 회전할 필요가 없습니다.

그림으로 보기

그림 출처: GimunLee/tech-refrigerator (Apache-2.0)

Python 코드

def selection_sort(arr):
    """자리마다 남은 값 중 최솟값을 골라 넣는 선택 정렬 (오름차순)"""
    n = len(arr)
    for i in range(n - 1):                 # 1.
        index_min = i
        for j in range(i + 1, n):          # 2.
            if arr[j] < arr[index_min]:    # 3.
                index_min = j
        arr[i], arr[index_min] = arr[index_min], arr[i]   # 4.
    return arr


print(selection_sort([4, 2, 5, 1]))
# 출력: [1, 2, 4, 5]

1. 먼저 값을 채울 위치(index) i를 선택합니다. 일단 그 자리의 값이 최솟값이라고 가정하고 index_min = i로 둡니다.
2. i + 1번째 원소부터 끝까지 돌면서, 지금까지의 최솟값과 비교를 시작합니다.
3. 오름차순이므로 순회 중인 값이 지금까지의 최솟값보다 작으면 index_min을 그 위치로 바꿉니다.
4. 2번 반복문이 끝나면 index_min에는 1번에서 고른 자리에 들어가야 할 값의 위치가 들어 있습니다. 그래서 두 값을 교환(swap)합니다.

시간복잡도와 공간복잡도

데이터 개수가 n개일 때 비교 횟수는 다음과 같습니다.

• 1회전: 1번 ~ (n-1)번 원소와 비교 → n-1번
• 2회전: 2번 ~ (n-1)번 원소와 비교 → n-2번
• …
• 합계: (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

비교가 상수 시간에 끝난다고 가정하면, n개를 정렬하는 데 O(n²)의 시간이 걸립니다. 배열이 이미 정렬되어 있어도 "남은 것 중 최솟값"을 확인하려면 끝까지 다 봐야 하므로 최선, 평균, 최악이 모두 같습니다. (O 표기법은 시간 복잡도 글 참고)

경우	시간복잡도
최선	O(n²)
평균	O(n²)
최악	O(n²)
공간	추가 메모리 O(1) (입력 포함 O(n))

• 공간: 주어진 배열 안에서 교환만 하므로 입력 배열 외에 추가로 드는 메모리는 O(1)입니다.
• 교환 횟수는 회전마다 최대 1번이라 전체 최대 n-1번, 즉 O(n)입니다. 비교는 많지만 교환은 적습니다.

장점과 단점

장점

• 거품 정렬과 마찬가지로 알고리즘이 단순합니다.
• 비교 횟수는 많지만 거품 정렬보다 실제 교환 횟수가 적어서, 교환이 많이 필요한 자료 상태에서 비교적 효율적입니다.
• 거품 정렬과 마찬가지로 배열 안에서 교환하는 방식이라 다른 메모리 공간이 필요 없습니다. → 제자리 정렬(in-place sorting)

단점

• 시간복잡도가 O(n²)이라 비효율적입니다.
• 불안정 정렬(Unstable Sort) 입니다. 멀리 떨어진 두 값을 한 번에 바꾸기 때문에 같은 값의 순서가 뒤집힐 수 있습니다.

불안정한 예를 하나 보겠습니다. 같은 값 5 두 개를 구분하려고 5a, 5b라고 이름 붙입니다.

회전	배열 상태	설명
시작	[5a, 5b, 2]	5a가 5b보다 앞
1회전	[2, 5b, 5a]	최솟값 2와 맨 앞 5a를 교환. 5a가 맨 뒤로 밀림
2회전	[2, 5b, 5a]	5b와 5a는 같은 값이라 교환 없음

정렬은 끝났지만 5a와 5b의 순서가 처음과 반대가 되었습니다.

마무리

거품 정렬과 비슷하지만 교환이 적어 조금 더 빠른 선택 정렬을 알아봤습니다. 기술 면접이나 시험("n번째 회전 후 배열 상태는?")에도 종종 나오는 정렬이니 알아 두면 좋습니다.

정리

개념	비전공자 버전 요약
선택 정렬	1등 자리부터 차례로, 남은 사람 중 가장 작은 값을 골라 세우기
회전(pass)	자리 하나를 확정하는 한 바퀴
교환 횟수	한 바퀴에 최대 한 번이라 적음
불안정 정렬	멀리 있는 값과 바꾸다 보니 같은 값 순서가 뒤집힐 수 있음

출처: GimunLee/tech-refrigerator (Apache-2.0), 코드는 Python으로 다시 작성

참고: jinhyy - 정렬 알고리즘