[알고리즘] 선택 정렬(Selection Sort)

k번째부터 마지막 원소 중 가장 작은 값을 선택해 k번째에 위치하게 한다. (k = 1, 2, 3, ...)

특징

선택 정렬이라는 이름은 남은 원소들 중 가장 작은 값을 매번 선택한다 하여 붙은 것이다.

n, n-1, n-2, ... , 1번으로 총 $\frac{n(n-1)}{2}$ 번의 비교 연산이 필요하다.
따라서 시간 복잡도는 O(N^2)이다.

데이터가 어떻게 정렬되어 있든 소모되는 비용이 일정하다.

버블 정렬의 경우 앞에서부터 값을 비교해 필요한 경우마다 스왑 연산을 진행한다면, 선택 정렬은 일단 앞에서부터 끝까지 한 번 훑은 후 스왑 연산을 진행하기 때문이다.

구현 [Python]

def selection_sort(a: List[int]) -> None:
    for start in range(len(a)):
        i_min = start
        for i in range(start + 1, len(a)):
            if a[i] < a[i_min]:
                i_min = i

        if i_min != start:
            a[start], a[i_min] = a[i_min], a[start]