선택 정렬

선택 정렬은 많은 사람이 손에 든 카드를 정리하는 방식으로 목록을 정렬합니다. 가장 작은 것을 찾아 맨 앞에 두고, 나머지 중에서 다시 가장 작은 것을 찾습니다. 비교는 많지만 교환은 아주 적고, 실행 시간은 목록의 순서에 거의 영향을 받지 않습니다.

높이가 다른 막대들을 정렬하는 모습. 왼쪽은 정렬된 부분이고, 남은 막대 중 가장 작은 막대가 강조되어 있으며, 화살표가 그 막대가 제자리로 교환되는 것을 보여 줍니다
높이가 다른 막대들을 정렬하는 모습. 왼쪽은 정렬된 부분이고, 남은 막대 중 가장 작은 막대가 강조되어 있으며, 화살표가 그 막대가 제자리로 교환되는 것을 보여 줍니다

기본 아이디어

목록을 왼쪽의 정렬된 부분(처음에는 비어 있음)과 오른쪽의 정렬되지 않은 부분으로 나눕니다. 정렬되지 않은 부분을 훑으며 가장 작은 값의 위치를 기억합니다. 그 값을 정렬되지 않은 첫 번째 값과 교환하면 정렬된 부분이 하나 늘어납니다. 값이 하나만 남을 때까지 반복하며, 마지막 값은 반드시 가장 큰 값입니다.

예시

5, 1, 4, 2, 8을 예로 들어 봅시다. 첫 번째 패스는 다섯 값을 모두 훑어 가장 작은 1을 찾고 5와 교환합니다: 1, 5, 4, 2, 8. 두 번째 패스는 5, 4, 2, 8을 훑어 2를 찾고 5와 교환합니다: 1, 2, 4, 5, 8. 세 번째 패스에서는 4가, 네 번째 패스에서는 5가 이미 제자리에 있으므로 아무것도 움직이지 않습니다. 비교는 4 + 3 + 2 + 1 = 10번, 교환은 2번뿐입니다. 같은 목록에서 버블 정렬은 4번 교환합니다.

비교 횟수는 항상 같다

어느 값이 가장 작은지 확신하려면 남은 값을 모두 봐야 합니다. 1번째 패스는 n − 1번, 2번째 패스는 n − 2번 비교하고, 이렇게 1번까지 내려가면 합계는 n(n − 1)/2번입니다. 이 횟수는 목록에 따라 달라지지 않습니다. 정렬된 목록도 역순 목록과 정확히 같은 횟수만큼 비교합니다. 선택 정렬에는 조기 종료가 없습니다. 가장 작은 값이 이미 맨 앞에 있다는 것을 알아내도 나머지에 대해서는 아무것도 알 수 없기 때문입니다.

적은 교환

각 패스는 교환을 최대 한 번 하므로, 선택 정렬의 교환은 n − 1번을 넘지 않으며 가장 작은 값이 이미 제자리에 있으면 교환을 건너뜁니다. 버블 정렬과 삽입 정렬은 순서가 뒤바뀐 쌍의 수만큼 교환하는데, 이는 약 n²/2번에 이를 수 있습니다. 쓸 때마다 닳는 메모리처럼 값을 쓰는 비용이 두 값을 읽는 비용보다 훨씬 클 때는 교환이 적다는 점이 장점입니다.

안정 정렬이 아니다

같은 값들이 원래 순서를 유지하면 안정 정렬이라고 합니다. 선택 정렬은 안정 정렬이 아닙니다. 멀리 떨어진 값과의 교환 때문에 어떤 값이 같은 값을 건너뛸 수 있기 때문입니다. 2, 2, 1에서 첫 번째 패스는 첫 번째 2와 1을 교환해 1, 2, 2가 되고, 두 2의 순서가 뒤바뀝니다. 교환 대신 사이의 값들을 밀어 옮기는 방식은 안정적이지만 훨씬 많은 값을 옮깁니다.

직접 해 보기

앱을 열고 ‘재생’을 누르거나, ‘단계’를 눌러 비교를 하나씩 진행하세요. 탐색 중인 값이 강조되고, 현재 최솟값은 따로 색이 표시되며, 각 패스는 왼쪽의 정렬된 부분으로 교환하며 끝납니다. 정렬된 목록과 역순 목록을 시도해 보세요. 비교 횟수는 같고 교환 횟수만 다릅니다.

자주 묻는 질문

선택 정렬의 시간 복잡도는?

모든 경우에 O(n²)입니다. n개의 값에 대해 순서와 상관없이 정확히 n(n − 1)/2번 비교합니다. 교환은 최대 n − 1번이고, 추가 메모리는 O(1)만 필요합니다.

선택 정렬과 버블 정렬의 차이는?

버블 정렬은 진행하면서 이웃한 값을 교환하고, 교환이 없는 패스가 나오면 일찍 멈출 수 있습니다. 선택 정렬은 가장 작은 값의 위치만 기억했다가 각 패스 끝에 한 번 교환합니다. 교환은 선택 정렬이 더 적고, 거의 정렬된 목록에서는 버블 정렬이 더 빠릅니다.

선택 정렬은 안정 정렬인가요?

아닙니다. 교환 때문에 어떤 값이 그와 같은 다른 값을 건너뛸 수 있어서, 같은 값들의 순서가 바뀔 수 있습니다. 교환 대신 값을 밀어 옮기면 안정적으로 만들 수 있지만 이동이 더 많아집니다.

힙 정렬은 선택 정렬과 어떤 관계인가요?

힙 정렬은 다음 값을 더 빨리 찾는 선택 정렬입니다. 정렬되지 않은 부분을 힙으로 유지하므로, 매번 전체를 훑는 대신 약 log n단계 만에 값을 고릅니다. 그래서 전체 시간이 O(n log n)으로 줄어듭니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

선택 정렬 해 보기