Selection Sort: 최소값을 찾고 교환하는 정렬 알고리즘
선택 정렬은 배열의 모든 요소를 순회하며 최소값을 찾아 현재 위치의 요소와 교환하는 방식으로 정렬을 수행합니다. 간단하지만 효율성은 떨어지는 알고리즘으로, 작은 데이터셋에 적합합니다. 불안정 정렬(Unstable Sort)에 속하며, 제자리 정렬(In-place Sort)입니다.
1. 개념
선택 정렬(Selection Sort)은 주어진 배열에서 최소값(또는 최대값)을 찾아 배열의 가장 앞(또는 뒤)으로 이동시키는 과정을 반복하여 배열을 정렬하는 알고리즘입니다. 각 단계마다 정렬되지 않은 부분에서 가장 작은(또는 큰) 요소를 선택하여 정렬된 부분의 끝에 위치시킵니다.
2. 왜 사용하는가
선택 정렬은 구현이 간단하다는 장점이 있습니다. 메모리 사용량도 적어 제자리 정렬(In-place Sort)이 가능합니다. 하지만 데이터의 양이 많아질수록 성능이 떨어지기 때문에, 일반적으로 큰 데이터셋에는 사용하지 않습니다. 학습용이나 작은 데이터셋을 정렬할 때 유용합니다.
3. 동작 원리
- 배열의 첫 번째 요소부터 시작하여 최소값을 찾습니다.
- 찾은 최소값을 배열의 첫 번째 요소와 교환합니다.
- 두 번째 요소부터 시작하여 다시 최소값을 찾습니다.
- 찾은 최소값을 두 번째 요소와 교환합니다.
- 이 과정을 반복하여 배열의 끝까지 정렬합니다.
4. 코드 예제
def selection_sort(arr):
"""
선택 정렬 알고리즘을 구현하는 함수
"""
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 예시
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print(sorted_arr) # 출력: [11, 12, 22, 25, 64]5. 시간 복잡도 또는 성능 특성
선택 정렬의 시간 복잡도는 다음과 같습니다.
- 최선의 경우: O(n^2)
- 평균의 경우: O(n^2)
- 최악의 경우: O(n^2)
데이터의 양이 증가함에 따라 시간 복잡도가 제곱으로 증가하므로, 큰 데이터셋에는 적합하지 않습니다. 공간 복잡도는 O(1)으로, 제자리 정렬(In-place Sort)입니다.
6. 실무 사용 사례
선택 정렬은 데이터의 양이 적은 경우, 또는 교육 목적으로 간단한 정렬 알고리즘을 이해하는 데 사용될 수 있습니다. 실무에서는 일반적으로 더 효율적인 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)이 사용됩니다.
7. 주의할 점
선택 정렬은 불안정 정렬(Unstable Sort)입니다. 즉, 동일한 값을 가진 요소의 순서가 정렬 후에 변경될 수 있습니다. 따라서 값의 순서가 중요한 경우에는 다른 안정 정렬(Stable Sort) 알고리즘을 사용하는 것이 좋습니다.
8. 핵심 정리
선택 정렬은 배열에서 최소값을 찾아 교환하는 방식으로 정렬을 수행하는 간단한 알고리즘입니다. 구현은 쉽지만, 시간 복잡도가 O(n^2)이므로 큰 데이터셋에는 적합하지 않습니다. 작은 데이터셋이나 교육 목적으로 활용할 수 있습니다.