선택 정렬
선택 정렬은 많은 사람이 손에 든 카드를 정리하는 방식으로 목록을 정렬합니다. 가장 작은 것을 찾아 맨 앞에 두고, 나머지 중에서 다시 가장 작은 것을 찾습니다. 비교는 많지만 교환은 아주 적고, 실행 시간은 목록의 순서에 거의 영향을 받지 않습니다.
기본 아이디어
목록을 왼쪽의 정렬된 부분(처음에는 비어 있음)과 오른쪽의 정렬되지 않은 부분으로 나눕니다. 정렬되지 않은 부분을 훑으며 가장 작은 값의 위치를 기억합니다. 그 값을 정렬되지 않은 첫 번째 값과 교환하면 정렬된 부분이 하나 늘어납니다. 값이 하나만 남을 때까지 반복하며, 마지막 값은 반드시 가장 큰 값입니다.
예시
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를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
선택 정렬 해 보기