선택 정렬 알고리즘

선택 정렬 알고리즘(selection sort)

1. 리스트 중에서 최소값을 찾습니다.
2. 그 값을 리스트의 맨 앞에 위치한 값과 바꿉니다.
3. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복합니다.

Python 코드

def selection_sort(arr: list[int]) -> list[int]:
    length: int = len(arr)
    # 배열 전체를 반복하면서
    for index_1 in range(length):
        min_index: int = index_1
        # 현재 위치에서 가장 작은 원소를 찾습니다.
        for index_2 in range(index_1 + 1, length):
            if arr[min_index] > arr[index_2]:
                min_index = index_2

        # 가장 작은 원소와 현재 원소를 교환합니다.
        arr[index_1], arr[min_index] = arr[min_index], arr[index_1]

    return arr


if __name__ == "__main__":
    arr: list[int] = [3, 1, 4, 9, 5, 7, 5]
    print(selection_sort(arr))
    # [1, 3, 4, 5, 5, 7, 9]

예를 들어, 이 함수에 [3, 1, 4, 9, 5, 7, 5] 배열을 전달하면,
3 과 1 을 비교해 1 이 더 작으므로 min_index은 0에서 1 의 위치정보인 1로 바뀝니다. 그리고 나머지 숫자들과 차례대로 비교합니다.
그러면 배열이 [1, 3, 4, 9, 5, 7, 5] 로 바뀝니다.
이러한 과정을 반복하면 배열 [1, 3, 4, 5, 5, 7, 9] 이라는 결과가 나옵니다.

선택 정렬의 시간 복잡도는 O(n^2)입니다. 이는 리스트의 모든 요소를 한 번씩 검사해야 하기 때문이며, 따라서 큰 리스트에서는 매우 느릴 수 있습니다.