정렬 알고리즘 중에서 가장 직관적이고 쉽게 구현이 가능한 선택 정렬(Selection Sort)에 대해서 알아보겠습니다.
기본 아이디어
선택 정렬은 알고리즘에 대해 배워본 적이 없는 사람도 쉽게 생각해낼 수 있는 정렬 알고리즘입니다. 왜냐하면 우리가 일상에서 무언가를 크기 순으로 나열할 때 흔히 사용되는 사고 방식이기 때문입니다.
170cm, 180cm, 150cm, 160cm예를 들어, 위와 같이 키를 알고 있는 네 친구들을 키 순으로 세우려면, 우선 4명의 키를 모두 비교하여 키가 제일 작은 150cm인 친구를 맨 앞에 세웁니다.
150cm (4명 중 제일 작음)키가 150cm인 친구는 맨 앞에 세웠으니, 이제 나머지 세 친구의 키를 비교하여 키가 제일 작은 160cm인 친구를 그 다음에 세웁니다.
150cm, 160cm (150cm 빼고 남은 3명 중 제일 작음)이제는 키가 170cm인 친구와 180cm인 친구 둘만 남았습니다. 둘 중에 170cm 친구가 더 작기 때문에 이 친구를 먼저 세우고, 그 다음 180cm인 친구를 마지막에 세웁니다.
150cm, 160cm, 170cm (150cm, 160cm 빼고 남은 2명 중 제일 작음), 180cm (키기 가장 큼)위에서 설명 정렬 방식을 일반해보면 다음과 같이 정리할 수 있습니다.
| Index | Value |
|---|---|
| 0 | 모든 값 중에서 가장 작은 값 |
| 1 | 첫 번째 값(Index=0)을 제외하고 남은 값 중에서 가장 작은 값 |
| … | … |
| i | i번째 부터 n-1 번째까지 값 중 가장 작은 값 |
| … | … |
| n-2 | n-2번째와 n-1 번째까지 값 중 가장 작은 값 |
| n-1 | 마지막에 남은 하나의 값 (비교 대상 없음) |
즉, 크기 n의 배열이 주어졌을 때, index 0부터 n-1까지의 모든 index i에 대해서, i번째 부터 n-1 번째까지 값 중 가장 작은 값을 구해서 index i에 놓으면 정렬된 배열을 얻을 수가 있습니다. 모든 index에 대해서 그 index에 위치시킬 값을 “선택”하기 때문에 이 정렬 알고리즘을 “선택 정렬”또는 “Selection Sort”이라고 부릅니다.
실전 예제
아래와 같이 1부터 5까지 총 5개의 숫자가 들어있는 배열을 위에서 설명한 선택 정렬 알고리즘을 이용하여 정렬을 해보겠습니다. i는 현재 index, m은 가장 작은 값이 있는 index를 가르킵니다.
i
[3, 4, 5, 1, 2]
m우선 index 0에 놓을 값을 찾아야 합니다. 모든 숫자 중 가장 작은 숫자인 1을 index 3에서 찾았습니다. 1을 index 0에 위치시키기 위해서 위해서 원래 index 0에 있던 3과 1의 자리를 바꿉니다.
i
[1, 4, 5, 3, 2]
m다음으로 index 1에 놓을 값을 찾아야 합니다. 1을 제외하고 남은 숫자 중에서 가장 작은 숫자인 2를 index 4에서 찾았습니다. 2를 index 1에 위치시키기 위해서 원래 index 1에 있던 4와 2의 자리를 바꿉니다.
i
[1, 2, 5, 3, 4]
m다음으로 index 2에 놓을 값을 찾아야 합니다. 1, 2를 제외하고 남은 숫자 중에서 가장 작은 숫자인 3를 index 3에서 찾았습니다. 3를 index 2에 위치시키기 위해서 원래 index 2에 있던 5와 3의 자리를 바꿉니다.
i
[1, 2, 3, 5, 4]
m다음으로 index 3에 놓을 값을 찾아야 합니다. 1, 2, 3를 제외하고 남은 숫자 중에서 가장 작은 숫자인 4를 index 4에서 찾았습니다. 4를 index 3에 위치시키기 위해서 원래 index 3에 있던 5와 4의 자리를 바꿉니다.
i
[1, 2, 3, 4, 5]
m마지막으로 index 4에 놓을 값을 찾아야 합니다. 1, 2, 3, 4를 제외한 남은 숫자는 5 밖에 없으며 따라서 지동으로 5가 가장 작은 숫자가 됩니다.
복잡도 분석
- 선택 정렬은 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에
O(1)의 공간 복잡도를 가집니다. - 시간 복잡도는 우선 루프문을 통해 모든 인덱스에 접근해야 하기 때문에 기본적으로
O(N)을 시간을 소모하며, 하나의 루프에서는 현재 인덱스의 값과 다른 인덱스의 값들과 비교하여 최소값을 찾은 후 현재 인덱스에 있는 값과 상호 자리 교대를(swap)해야 해야하기 때문에O(N)을 시간이 필요하게 됩니다. 따라서 선택 정렬은 총O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘입니다.
알고리즘 특징
- 선택 정렬은 정렬된 값을 배열의 맨 앞부터 하나씩 채워나가게 됩니다. 따라서, 뒤에 있는 index로 갈수록 비교 범위가 하나씩 점점 줄어드는 특성을 가지고 있습니다. (index 0에서는 0부터 n-1까지 비교해야 되지만, index n-1에서는 남은 숫자가 하나 밖어서 비교가 필요 없음)
- 입력 배열이 이미 정렬되어 있건 말건 관계없이 동일한 연산량을 가지고 있기 때문에 최적화 여자가 적어서 다른
O(N^2)대비해도 성능이 떨어지는 편입니다. - 이러한 성능 상의 한계 때문에 실전에서는 거의 보기 힘들지만, 가장 구현이 쉬운 정렬 알고리즘이라서, 알고리즘 수업 시간에는 한 번씩 꼭 접하게 되는 유명한 정렬 알고리즘입니다.
구현
두 개의 반복문이 필요합니다. 내부 반복문에서는 현재 index부터 마지막 index까지 최소값의 index를 찾아내고, 외부 반복문에서는 이 최소값의 index와 현재 index에 있는 값을 상호 교대(swap)합니다. 외부 반복문에서는 index i를 0에서 n-2(또는 n-1. 마지막 index에서는 남는 값이 하나 밖에 없기 때문에 대세에 지장 없음)까지 진행시키며, 내부 반복문에서 이미 정렬된 값들에서는 관심이 없기 때문에 index j를 i에서 n-1까지 진행시킵니다. 각 index에 대해서 최소값을 찾기 위해 대소 비교는 여러번 일어나나 상호 교대(swap)은 딱 한번만 알어납니다.
Python 코드
def selection_sort(arr):
for i in range(len(arr) - 1):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]Java 코드
public class Selection {
public static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx])
minIdx = j;
}
swap(arr, i, minIdx);
}
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}마치면서
정렬 알고리즘의 가장 기본이라고 할 수 있는 선택 정렬에 대해서 알아보았습니다. 앞으로 다른 정렬 알고리즘에 대해서도 포스팅하도록 하겠습니다.