[python] 선택 정렬
선택 정렬(Selection Sort)은 주어진 리스트에서 가장 작은 값을 찾아 첫 번째로 위치시키고, 그 다음으로 작은 값을 두 번째로 위치시키는 과정을 반복하여 정렬하는 알고리즘입니다. 선택 정렬은 작은 크기의 리스트에 대해서는 효율적인 정렬 알고리즘입니다.
알고리즘 동작원리
- 주어진 리스트에서 첫 번째 값부터 마지막 값까지 반복합니다.
- 현재 인덱스의 값을 최소값으로 가정합니다.
- 최소값을 찾기 위해 현재 인덱스부터 마지막 값을 비교합니다.
- 만약 비교한 값이 현재 최소값보다 작다면 해당 값을 새로운 최소값으로 설정합니다.
- 비교가 종료되면 현재 인덱스의 값과 최소값을 교환합니다.
- 모든 인덱스에 대해 반복하면 정렬된 리스트가 완성됩니다.
코드 예시
def selection_sort(arr):
for i in range(len(arr)):
min_index = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# 사용 예시
arr = [5, 3, 8, 2, 1]
sorted_arr = selection_sort(arr)
print(sorted_arr) # [1, 2, 3, 5, 8]
시간복잡도
선택 정렬의 시간복잡도는 O(n^2)입니다. 매번 최소값을 찾기 위해 비교를 수행하고, 이를 리스트의 크기만큼 반복하기 때문에 n * (n-1) / 2 번의 비교를 수행하게 됩니다. 이러한 이유로 선택 정렬은 큰 크기의 리스트에 대해서는 비효율적인 알고리즘이라고 볼 수 있습니다.
결론
선택 정렬은 구현이 간단하고 이해하기 쉬운 정렬 알고리즘입니다. 하지만, 크기가 큰 리스트에 대해서는 비효율적이므로, 실제 사용시에는 다른 정렬 알고리즘을 고려하는 것이 좋습니다.