[Python]선택 정렬(Selection Sort)

---

선택 정렬이란?

선택 정렬은 가장 간단한 정렬 알고리즘 중 하나입니다. 리스트에서 가장 작은(또는 큰) 원소를 선택해 알맞은 위치로 옮기는 과정을 반복하여 정렬을 완성합니다.

---

선택 정렬을 사용하는 이유

선택 정렬은 구현이 간단하며 이해하기 쉬운 알고리즘입니다. 데이터가 비교적 적을 때 효과적으로 동작하며, 추가적인 메모리 공간을 거의 사용하지 않습니다.

---

선택 정렬의 사용법

1. 리스트에서 가장 작은 원소를 찾습니다.

2. 해당 원소를 리스트의 맨 앞에 위치한 원소와 교환합니다.

3. 정렬된 부분 리스트를 제외하고 나머지 리스트에서 위 과정을 반복합니다.

---

선택 정렬 예시

예를 들어, 리스트 [64, 25, 12, 22, 11]을 선택 정렬로 정렬하는 과정은 다음과 같습니다:

1. [64, 25, 12, 22, 11]에서 가장 작은 원소는 11입니다. 따라서 [11, 25, 12, 22, 64]가 됩니다.

2. 다음으로 [25, 12, 22, 64]에서 가장 작은 원소는 12입니다. [12, 25, 22, 64]가 됩니다.

3. 이 과정을 반복하여 최종적으로 정렬된 리스트는 [11, 12, 22, 25, 64]가 됩니다.

---

선택 정렬을 사용할 때 주의할 점

선택 정렬은 비교적 큰 데이터에 대해서는 성능이 떨어질 수 있습니다. 이 알고리즘은 모든 경우에서 O(n^2)의 시간 복잡도를 가지기 때문에, 데이터가 많은 경우에는 다른 정렬 알고리즘을 고려하는 것이 좋습니다.

---

코드 예시

이제 파이썬 코드를 통해 선택 정렬을 구현해 보겠습니다:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 최솟값을 찾기 위한 인덱스 설정
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 최솟값을 현재 인덱스와 교환
        arr[i], arr[min_index] = arr[min_index], arr[i]

# 예시
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("정렬된 배열:", arr)