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

선택 정렬은 각 반복에서 정렬되지 않은 목록에서 가장 작은 요소를 선택하고 해당 요소를 정렬되지 않은 목록의 시작 부분에 배치하는 정렬 알고리즘 이다.

선택 정렬 알고리즘 순서

Ex) 20, 12, 10, 15, 2

1. 첫 번째 요소를 최소값(minimum)으로 설정한다.

(20), 12, 10, 15, 2

첫 번째 값이 최소값(20)으로 선택한다.

2. 최소값(20)과 두 번째 요소(12)와 비교한다. 두 번째 요소(12)가 최소값(20) 보다 작으므로 최소값(12)으로 바뀐다.

20, 12, 10, 15, (2)

3. 이 과정을 반복해서 하다보면 실제로 최소값(2)은 가 나오게 되고 이 값을 첫 번째 요소(20)와 변경한다.

(2), 12, 10, 15, 20

4. 첫 번째 요소는 정렬이 끝났으니 다시 두번째 요소를 최소값(12)로 잡고 비교를 해서 최소값을 찾아낸다. 그리고 정렬이 끝 난 요소 후의 인덱스 값과 변경 하는 것을 반복해서 정렬을 진행한다.

(2), 10, 12, 15, 20

시간 복잡도

초반에 두개씩 비교해서 값을 찾아내는 과정이 얼핏 버블 정렬과 유사하다는 것을 알수 있다.

def selection_sort(arr):
    n = len(arr)

    for i in range(n - 1):
        # 현재 인덱스를 최솟값으로 설정
        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]

# 사용 예시
my_list = [2, 12, 10, 15, 20]
selection_sort(my_list)

print("정렬된 리스트:", my_list)

처음에 min_index로 최소값을 설정하고 나머지 원소들과 swap이 아닌 인덱스만 갱신을 해주고 마지막에 swap은 한번만 일어나게 된다. 결국 이중 반복문을 돌게 되는 구조가 되므로 시간 복잡도 O(n^2)이 된다고 할수가 있다.

선택 정렬도 버블 정렬과 같이 최적화를 할수가 있다.

<선택 정렬 최적화>

def selection_sort(arr):
    n = len(arr)

    for i in range(n - 1):
        # 현재 인덱스를 최솟값으로 설정
        min_index = i

        # 나머지 원소들과 비교하여 최솟값의 인덱스 갱신
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # 현재 인덱스와 최솟값의 인덱스가 다를 때만 교환
        if i != min_index:
            arr[i], arr[min_index] = arr[min_index], arr[i]

# 사용 예시
my_list = [64, 34, 25, 12, 22, 11, 90]
selection_sort(my_list)

print("정렬된 리스트:", my_list)

이렇게 처리하면 현재 인덱스와 최소값의 인덱스가 같을 때 교환을 해야하는 불필요한 교환을 줄일수가 있다.