선택 정렬

선택 정렬은 뒤섞인 값을 작은 것부터 차례로 늘어놓습니다. 남은 값을 모두 훑어 가장 작은 값을 고릅니다. 고른 값은 앞쪽 끝으로 보냅니다. 값을 옮기는 횟수는 적습니다. 대신 비교는 입력이 어떻든 많이 합니다.

상세

이 절은 선택 정렬의 절차를 값 네 개로 따라가고 코드로 옮깁니다. 그다음 시간·메모리·같은 값끼리의 순서, 쓰는 곳과 피하는 곳을 봅니다.

받는 것과 내주는 것

값을 순서대로 늘어놓는 일을 정렬이라고 합니다. 선택 정렬은 그 일을 하는 절차 가운데 하나입니다. 넣는 것은 값을 번호 순서대로 나란히 담은 배열입니다. 나오는 것은 같은 값들이 작은 것부터 놓인 배열입니다.

두 값 가운데 어느 쪽이 앞인지는 비교로 가립니다. 숫자라면 작은 쪽이 앞입니다. 주문처럼 필드가 여럿인 값이라면 금액이나 주문 시각 같은 기준 하나를 골라 비교합니다.

키 순서로 줄 세우기

체육 시간에 학생들을 키 순서로 줄 세우는 장면을 떠올려 봅니다. 선생님은 아직 줄에 서지 않은 학생들을 한 번 쭉 둘러봅니다. 그중 가장 작은 학생을 불러 줄 맨 끝에 세웁니다. 남은 학생이 없어질 때까지 이 일을 되풀이하면 줄이 키 순서로 완성됩니다.

정렬된 앞부분과 남은 뒷부분

선택 정렬은 배열을 두 부분으로 나눠 봅니다. 왼쪽은 순서가 이미 정해진 정렬된 앞부분입니다. 오른쪽은 아직 정렬하지 않은 남은 뒷부분입니다. 처음에는 배열 전체가 남은 뒷부분입니다.

한 차례가 끝날 때마다 앞부분이 한 칸 늘어납니다. 새로 붙는 값은 뒷부분에서 가장 작은 값입니다. 그래서 앞부분의 값은 언제나 뒷부분의 어느 값보다도 작거나 같습니다.

이 성질 덕분에 한 번 앞부분에 들어간 값은 다시 움직이지 않습니다. 뒷부분에서 더 작은 값이 나올 일이 없기 때문입니다. 앞부분은 늘어나기만 합니다.

한 차례에 하는 일

한 차례는 두 단계입니다. 먼저 남은 뒷부분에서 가장 작은 값을 찾습니다. 그다음 그 값을 뒷부분의 맨 앞 값과 맞바꿉니다.

가장 작은 값은 뒷부분을 처음부터 끝까지 한 번 훑어 찾습니다. 뒷부분 맨 앞 값을 일단 후보로 둡니다. 다음 값부터 하나씩 후보와 비교합니다. 후보보다 작은 값을 만나면 그 값이 새 후보가 됩니다.

끝까지 훑고 나면 후보가 뒷부분에서 가장 작은 값입니다. 이 값을 뒷부분 맨 앞 값과 맞바꿉니다. 맞바꾸기는 두 칸에 든 값을 서로 바꿔 넣는 일입니다. 후보가 이미 뒷부분 맨 앞에 있으면 바꿀 것이 없습니다.

뒷부분에 값이 하나만 남으면 정렬이 끝납니다. 남은 그 값은 전체에서 가장 큰 값입니다. 이미 맨 끝에 있으니 할 일이 없습니다.

아래 그림은 이 과정을 한 장으로 보입니다. 위쪽 고리는 후보를 찾는 훑기입니다. 아래쪽 물음은 다음 차례로 넘어갈지를 정합니다.

flowchart TD
    A["뒷부분 맨 앞 값을 후보로 둔다"] --> B{"다음 값이 후보보다 작은가"}
    B -->|예| C["그 값을 새 후보로 삼는다"]
    B -->|아니오| D{"뒷부분 끝까지 봤나"}
    C --> D
    D -->|아니오| B
    D -->|예| E["후보와 뒷부분 맨 앞 값을 맞바꾼다"]
    E --> F{"뒷부분에 값이 둘 이상 남았나"}
    F -->|예| A
    F -->|아니오| G["정렬 끝"]

값 네 개를 정렬해 보기

배열 4, 2, 5, 1 을 정렬해 봅니다. 시작할 때는 네 값 모두 남은 뒷부분입니다. 아래 표의 한 줄이 한 차례입니다.

첫 차례는 네 값을 모두 훑습니다. 후보는 4 에서 2 로, 다시 1 로 바뀝니다. 그다음 맨 앞의 4 와 맨 끝의 1 을 맞바꿉니다. 4 는 한 번에 세 칸을 건너 맨 끝으로 갑니다.

둘째 차례의 가장 작은 값 2 는 이미 뒷부분 맨 앞에 있습니다. 그래서 바꿀 것이 없습니다. 그래도 5 와 4 를 모두 훑어 본 뒤에야 이것을 압니다.

셋째 차례에서 5 와 4 를 맞바꾸면 뒷부분에 5 하나만 남습니다. 정렬이 끝납니다. 배열은 1, 2, 4, 5 가 됩니다.

후보와 견주는 비교는 훑은 값보다 하나 적습니다. 첫 값은 후보로 두기만 하기 때문입니다. 네 값, 세 값, 두 값을 훑었으니 비교는 3 + 2 + 1, 모두 여섯 번입니다. 맞바꾸기는 두 번 했습니다.

코드로 옮긴 선택 정렬

같은 절차를 파이썬으로 옮기면 아래와 같습니다. 바깥 for 한 바퀴가 표의 한 차례입니다. 안쪽 for 가 가장 작은 값을 찾는 훑기입니다.

def 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
        a[i], a[m] = a[m], a[i]
    return a

a = [4, 2, 5, 1]
selection_sort(a)  # [1, 2, 4, 5]

i 는 남은 뒷부분의 맨 앞 번호입니다. m 은 지금까지 찾은 후보의 번호입니다. 안쪽 반복이 끝나면 a[i] 와 a[m] 을 맞바꿉니다. 둘째 차례처럼 i 와 m 이 같으면 한 칸을 자기 자신과 바꿉니다. 배열은 바뀌지 않습니다.

바깥 반복은 n - 1 번 돕니다. 뒷부분에 값이 하나 남으면 훑을 필요가 없기 때문입니다.

걸리는 시간

걸리는 시간은 비교와 맞바꾸기를 몇 번 하느냐로 정해집니다. 선택 정렬에서는 두 횟수가 입력 모양에 거의 휘둘리지 않습니다. 이 소절은 두 횟수를 따로 셉니다.

값의 개수를 n 이라고 적습니다. 빅오 표기법은 n 이 늘 때 시간이 어떤 모양으로 느는지를 적는 약속입니다. O(n) 은 n 이 두 배가 되면 시간도 두 배쯤 된다는 뜻입니다. O(n²) 은 n 이 두 배가 되면 시간이 네 배쯤 된다는 뜻입니다.

비교부터 셉니다. 첫 차례는 값 n 개를 훑습니다. 비교는 n − 1 번입니다. 다음 차례는 n − 2 번, 그다음은 n − 3 번입니다. 모두 더하면 (n − 1) + (n − 2) + … + 1, 곧 n(n − 1)/2 번입니다. 이것이 O(n²) 입니다.

이 횟수는 입력이 어떻든 같습니다. 이미 정렬된 배열이 들어와도 가장 작은 값이 맨 앞에 있는지는 끝까지 훑어야 압니다. 거꾸로 정렬된 배열도 비교 횟수는 똑같습니다.

가장 일찍 끝나는 입력을 최선의 경우, 가장 오래 걸리는 입력을 최악의 경우라고 부릅니다. 선택 정렬은 두 경우가 모두 O(n²) 입니다.

맞바꾸기는 한 차례에 많아야 한 번입니다. 차례가 n − 1 번이니 맞바꾸기도 많아야 n − 1 번, 곧 O(n) 입니다. 비교는 많이 해도 값을 옮기는 일은 적습니다.

값이 1,000 개일 때로 세어 봅니다. 비교는 499,500 번입니다. 맞바꾸기는 많아야 999 번입니다. 값이 2,000 개가 되면 비교는 약 200만 번으로 네 배쯤 늡니다.

입력이 이미 정렬된 정도에 따라 시간이 줄어드는 정렬을 적응형 정렬이라고 합니다. 선택 정렬은 적응형 정렬이 아닙니다. 거의 정렬된 데이터가 자주 들어와도 덕을 보지 못합니다.

따로 쓰는 메모리

선택 정렬은 입력 배열 안에서 값을 맞바꿔 정렬합니다. 따로 쓰는 메모리는 i, j, m 같은 변수 몇 개뿐입니다. 배열이 커져도 이 몇 칸은 늘지 않습니다. n 과 상관없이 일정한 공간을 O(1) 이라고 적습니다.

입력 배열 말고는 추가 공간이 거의 필요 없는 정렬을 제자리 정렬이라고 합니다. 선택 정렬은 제자리 정렬입니다. 그래서 메모리가 빠듯한 곳에서도 쓸 수 있습니다.

모든 정렬이 제자리 정렬은 아닙니다. 병합 정렬은 배열을 반씩 쪼갰다가 정렬된 조각을 합치는 정렬입니다. 합칠 때 배열 크기만큼 공간을 더 씁니다.

같은 값끼리의 순서

같은 값끼리는 원래 앞에 있던 값이 정렬 뒤에도 앞에 남는 정렬이 있습니다. 이런 정렬을 안정 정렬이라고 합니다. 주문 시각 순으로 쌓인 주문을 금액으로 다시 정렬한다고 해 봅니다. 안정 정렬이면 금액이 같은 주문끼리는 먼저 들어온 주문이 계속 앞에 섭니다.

배열에서 맞바꾸기로 도는 선택 정렬은 안정 정렬이 아닙니다. 맞바꾸기는 뒷부분 맨 앞 값을 뒤쪽 멀리 보냅니다. 그 값이 가는 길에 자기와 같은 값을 건너뛸 수 있습니다.

배열 2ᵃ, 2ᵇ, 1 로 봅니다. 2ᵃ 와 2ᵇ 는 같은 값 2 입니다. 원래 2ᵃ 가 앞에 있습니다. 아래 그림이 두 차례 동안 배열이 바뀌는 모습입니다.

flowchart TD
    S0["2ᵃ · 2ᵇ · 1"] -->|"첫 차례 · 1 과 2ᵃ 를 맞바꾼다"| S1["1 · 2ᵇ · 2ᵃ"]
    S1 -->|"둘째 차례 · 2ᵇ 가 후보로 남아 바꿀 것 없음"| S2["1 · 2ᵇ · 2ᵃ"]

첫 차례에서 2ᵃ 는 2ᵇ 를 건너 맨 끝으로 갑니다. 둘째 차례의 비교는 후보보다 작을 때만 후보를 바꿉니다. 같은 값인 2ᵃ 는 후보가 되지 못하므로 앞의 2ᵇ 가 후보로 남습니다. 결과는 1, 2ᵇ, 2ᵃ 로 두 값의 순서가 뒤집혔습니다.

순서를 지키게 고칠 수는 있습니다. 가장 작은 값을 맞바꾸는 대신 꺼내서 뒷부분 맨 앞에 끼웁니다. 그 사이 값들은 한 칸씩 뒤로 옮깁니다. 그러면 순서는 지켜집니다. 대신 값을 옮기는 횟수가 크게 늘어 맞바꾸기가 적다는 장점을 잃습니다.

삽입 정렬과 견주기

선택 정렬과 가장 자주 견주는 것은 삽입 정렬입니다. 삽입 정렬은 값을 하나씩 꺼내 이미 줄 세운 앞부분의 알맞은 위치에 끼워 넣는 정렬입니다. 둘 다 절차가 단순합니다. 걸리는 시간도 둘 다 O(n²) 입니다. 두 정렬이 어디서 갈리는지 아래 표로 봅니다.

두 정렬은 비용을 치르는 곳이 서로 반대입니다. 선택 정렬은 비교를 늘 많이 하는 대신 값을 거의 옮기지 않습니다. 삽입 정렬은 거의 정렬된 입력에서 비교와 옮기기가 모두 줄어듭니다. 대신 뒤섞인 입력에서는 값을 많이 옮깁니다.

선택 정렬을 쓰는 곳

이 소절은 선택 정렬이 쓸모 있는 두 경우를 봅니다. 값을 옮기는 일이 비쌀 때와 값이 몇 개 안 될 때입니다.

값을 옮기는 일이 비교보다 훨씬 비쌀 때 맞바꾸기가 적은 것이 이득이 됩니다. 값 하나가 큰 레코드여서 옮길 때마다 많은 바이트를 복사해야 하는 경우가 그렇습니다. 플래시 메모리처럼 쓸 수 있는 횟수에 한도가 있는 저장 장치에서도 같은 이유로 이 성질이 쓸모 있습니다.

값이 몇 개 안 되는 배열에서는 O(n²) 이라도 금방 끝납니다. 코드가 짧습니다. 추가 메모리도 들지 않습니다. 그래서 정렬을 처음 배울 때 삽입 정렬, 버블 정렬과 함께 먼저 다루는 경우가 많습니다.

고르는 일을 빠르게 한 힙 정렬

선택 정렬에서 시간을 잡아먹는 것은 가장 작은 값을 찾는 훑기입니다. 차례마다 뒷부분 전체를 훑기 때문입니다. 이 훑기를 빠르게 바꾼 것이 힙 정렬입니다.

힙 정렬은 값을 힙에 담습니다. 힙은 가장 크거나 가장 작은 값을 빨리 꺼내 주는 자료구조입니다. 남은 값을 전부 훑지 않아도 가장 작은 값을 꺼낼 수 있습니다.

log n 은 n 을 절반씩 나누어 1 에 닿기까지 나눈 횟수입니다. n 이 1,000 이면 10 번쯤입니다. 힙에서 값을 하나 꺼낼 때 드는 비교는 이 log n 번쯤입니다. 선택 정렬의 훑기에 드는 n 번쯤보다 훨씬 적습니다.

값 n 개를 하나씩 꺼내니 힙 정렬 전체는 O(n log n) 입니다. O(n log n) 은 n 이 두 배가 되면 시간이 두 배를 조금 넘게 는다는 뜻입니다.

힙 정렬은 흔히 가장 큰 값을 골라 맨 뒤로 보냅니다. 방향만 반대입니다. 남은 값에서 하나를 골라 한쪽 끝으로 보내는 생각은 선택 정렬과 같습니다.

선택 정렬을 피하는 곳

값이 많으면 O(n²) 이 그대로 드러납니다. 값이 백만 개면 비교가 약 5천억 번입니다. 같은 배열을 O(n log n) 정렬은 수천만 번 단위의 일로 끝냅니다.

그런 배열에는 병합 정렬이나 힙 정렬을 씁니다. 퀵 정렬도 대개 그만큼에 끝납니다. 퀵 정렬은 배열에서 값 하나를 골라 기준값으로 삼습니다. 그보다 작은 값과 큰 값을 양쪽으로 나눠 가며 정렬합니다.

실무에서는 이런 정렬을 직접 짜지 않습니다. 파이썬의 sorted(), 자바의 Arrays.sort() 처럼 표준 라이브러리의 정렬 함수를 부르면 됩니다.

거의 정렬된 데이터가 자주 들어오면 삽입 정렬이 더 일찍 끝납니다. 선택 정렬은 입력이 거의 정렬돼 있어도 비교를 줄이지 못합니다. 같은 값끼리의 순서를 지켜야 할 때는 안정 정렬을 고릅니다.

관련 항목

선택 정렬이 속하는 상위 분류

알고리즘 · 정렬 알고리즘 · 정렬 · 비교 정렬

선택 정렬 대신 쓸 수 있는 정렬 알고리즘

삽입 정렬 · 버블 정렬 · 병합 정렬 · 퀵 정렬 · 셸 정렬 · 계수 정렬 · 기수 정렬

선택 정렬의 고르기를 고쳐 만든 변형

힙 정렬 · 양방향 선택 정렬 · 안정 선택 정렬 · 토너먼트 정렬

선택 정렬을 가늠하는 정렬의 성질

안정 정렬 · 제자리 정렬 · 적응형 정렬 · 온라인 알고리즘

선택 정렬의 비용을 재는 표기

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 점근 표기법

선택 정렬이 안에서 쓰는 연산

최솟값 · 순차 탐색 · 스왑 · 비교 함수 · 정렬 키

선택 정렬이 값을 담아 도는 자료구조

배열 · 연결 리스트 · 동적 배열 · 힙

선택 정렬과 이름이 겹치는 헷갈리는 이웃

선택 알고리즘 · 퀵셀렉트 · 중앙값의 중앙값