선택 정렬(Selection sort)
- 단순 정렬(Simple sort) 중 하나로, 속도는 느린 편(평균적으로 O(n^{2}),
quadratic time)이지만 최악의 경우를 가정했을 때 버블소트보다 2배 가량 빠르다.
가정
- 배열(Array) 정렬을 가정한다.
- 정렬되지 않은 배열을 오름차순으로 정렬한다.
- 배열의 길이는 n이다.
순서
- index 0 원소를 temp라는 변수에 저장한다.
- 그 다음 index 1부터 index n-1 까지 순회하면서 temp보다 작은 값이 있는지 비교 한다. 만약 비교 결과 temp보다 작은 값이 있으면 그 값을 temp에 재할당한다. 이렇게 한 번 패스 스루(정해진 범위의 배열을 한 번 훑는 것)를 끝내고 나면, temp에는 전체 배열 원소값 중 최소값이 저장되어 있을 것이다.
- 이 최소값이 갖고 있던 index가 0 이 아니고 i라면, index 0과 index i의 원소를 교환하여 최소값이 배열의 맨 앞자리에 위치하도록 한다.
- 그 다음부터는 index 1부터 위 과정을 반복한다. 그러면 index 1부터 index n-1 사이(정렬되지 않은 범위)에서의 최소값이 index 1에 위치한다.
- 이 과정을 index 2, 3, 4… n-2가 될때까지 반복한다.
*
구현 - 파이썬
def selection_sort(list):
start_index = 0
while not start_index == len(list)-1:
temp = list[start_index]
temp_index = start_index
for i in range(start_index, len(list)):
if temp > list[i]:
temp = list[i]
temp_index = i
list[start_index], list[temp_index] = list[temp_index], list[start_index]
start_index += 1
return list
주의점
* 버블소트와 마찬가지로 셀렉션소트도 비교와 교환으로 이루어져 있다. 둘 다 오름차순으로 배열을 정렬하는데, 버블소트는 최대값을 배열 끝에서부터 하나씩 정렬하고, 셀렉션소트는 최소값을 배열 앞에서부터 하나씩 정렬한다. 다만 버블소트와 비교하자면 비교는 동일한 횟수만큼 일어나지만 교환 횟수가 셀렉션소트가 훨씬 적다. (최악의 경우를 가정할 때)
| * | Bubble Sort | Selection Sort |
|---|---|---|
| 비교 연산 | n(n-1) / 2 | n(n-1) / 2 |
| 교환 연산 | n(n-1) / 2 | n-1 |
빅오표기법으로는 같은 quadratic time으로 같은 분류에 해당하지만, 실제로는 셀렉션소트가 더 빠를 가능성이 높은 것이다. 평균적으로 약 2배 가량 빠르다고 한다. 즉 빅오표기법은 다른 분류 사이에서는 어느 것이 더 효율적인지 확실히 답해줄 수 있지만, 같은 분류 사이에서는 어떤 것이 더 효율적인지 말해주지 않는다.