선택 정렬
선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나입니다. 배열 A[1, …, n]에서 가장 작은(or 큰) 원소를 찾아 배열의 첫(or 끝)자리에 있는 \(A[1](or A[n])\)과 자리를 바꿉니다. \(A[1](or A[n])\) 원소에 대한 배열은 끝났으므로 나머지 원소를 대상으로 같은 작업을 반복합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 초기 min_idx = i = 0
# 새로운 min_idx = j = 1
i
[5, 3, 15, 34, 22, 45]
m
# min_idx[i] = 5 > min_idx[j] = 3
# 따라서 두 개 값 위치를 변경함
[3, 5, 15, 34, 22, 45]
# idx = 0 위치는 정렬되었으므로, 다음 idx부터 위 과정 반복
i
[3, 5, 15, 34, 22, 45]
m
i
[3, 5, 15, 34, 22, 45]
m
i
[3, 5, 15, 34, 22, 45]
m
i
[3, 5, 15, 22, 34, 45]
m
i
[3, 5, 15, 22, 34, 45]
m
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 정렬 대상 배열
array = [5, 3, 15, 34, 22, 45]
array_len = len(array)
# 배열 길이만큼 for loop 실행
for i in range(len(array)):
# min value index
min_idx = i
for j in range(i+1, array_len):
# 만약 새로운 min value 발견하면
if (array[min_idx] > array[j]):
# min value index 변경
min_idx = j
# min value 자리 변경
array[i], array[min_idx] = array[min_idx], array[i]
print(array)
시간 복잡도
선택 정렬의 수행 시간은 모든 경우에 \(\theta(n^{2})\) 입니다.
우선 첫 번째 for loop에서 모든 index에 접근해야 하므로 (n)번 수행합니다. 이제 min_idx를 제외한 나머지 (n-1)개 index를 탐색하므로 (n-1)번 수행합니다. 따라서 min_idx를 비교하는 총 횟수는 \((n-1)+(n-2)+...+2+1 = \frac{n(n-1)}{2}\) 입니다. 시간 복잡도는 \(\theta(n^{2})\) 입니다.