1. 선택 정렬 개념
기준이 되는 원소를 맨 처음 원소로 정합니다.
기준 원소로부터 맨 마지막 원소까지 탐색하여 최소값을 가지는 원소를 찾습니다.
기준 원소가 최소값이 아닐 경우 해당 원소와 자리를 바꿉니다.(제자리 정렬)
이 과정을 거치면 배열에서 가장 작은 값이 첫 번째 자리에 위치하게 됩니다.
따라서 기준이 되는 원소를 순차적으로 바꿔가며 위 과정을 반복합니다.
2. 선택 정렬 예제
3. 선택 정렬 코드
nums = [5, 3, 4, 1, 2]
def selection_sort(nums):
for i in range(len(nums)-1):
index_min = i
for j in range(i+1, len(nums)):
if nums[index_min] > nums[j]:
index_min = j
nums[i], nums[index_min] = nums[index_min], nums[i]
selection_sort(nums)
print(nums)
# [1, 2, 3, 4, 5]4. 선택 정렬 장점
선택 정렬은 직관적으로 이해하기 쉽고 구현하기가 간단한 알고리즘입니다.
제자리 정렬(In-place Sorting)이기 때문에 추가 메모리 공간을 거의 사용하지 않습니다.
5. 선택 정렬 단점
선택 정렬의 시간 복잡도는 최선, 최악, 평균 모두 \(O(n^2)\)으로 원소의 개수가 많아질수록 성능이 급격히 저하됩니다.
선택 정렬은 안정적이지 않은 정렬입니다. 따라서 동일한 값을 가진 원소들의 상대적인 순서가 유지되지 않을 수 있습니다.
6. 정렬 알고리즘 시간 복잡도 비교
| 정렬 알고리즘 | 최악(Worst) | 최선(Best) | 평균(Average) |
| 버블 정렬(Bubble Sort) | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) |
| 선택 정렬(Selection Sort) | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) |
| 삽입 정렬(Insertion Sort) | \(O(n^2)\) | \(O(n)\) | \(O(n^2)\) |
| 퀵 정렬(Quick Sort) | \(O(n^2)\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 병합 정렬(Merge Sort) | \(O(n\log{n})\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 힙 정렬(Heap Sort) | \(O(n\log{n})\) | \(O(n\log{n})\) | \(O(n\log{n})\) |
| 기수 정렬(Radix Sort) | \(O(n)\) | \(O(n)\) | \(O(n)\) |
| 계수 정렬(Counting Sort) | \(O(n)\) | \(O(n)\) | \(O(n)\) |
