[Algorithm] 선택 정렬 (Selection Sort)

array = [5,3,2,1,4]

for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]

print(array)

 

선택 정렬의 원리: 가장 작은 데이터를 선택하여 앞에 있는 데이터를 바꿔치기 하는 것을 (n-1)번 반복한다.

 

다음과 같은 배열이 있다고 하자. 

현재 맨 앞의 데이터와 배열에서 가장 작은 원소인 1을 교환한다.

1은 이미 정렬된 인덱스 이므로 제외한다.두번째 인덱스 3과 나머지 원소들 중 가장 작은 원소인 2를 교환한다.

1과 2는 이미 정렬되었으므로 제외한다.그런데 3은 이미 제자리에 와있으므로 교환이 이루어지지 않는다.

남아있는 원소들 중 가장 작은 4와 5의 위치를 바꿔준다. 

마지막 데이터는 가만히 두어도 이미 정렬된 상태이다. 이로써 배열이 오름차순으로 정렬되었다.

시간 복잡도는 O(N^2) 이다. 

N-1 번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다 . (마지막 인덱스는 자동으로 정렬되므로 n-1번이다.)

또한 매번 가장 작은 수를 비교하기 위해서 비교 연산이 필요하다. 

따라서 연산횟수는 N + (N-1) + (N-2) + ... + 2 = N(N+1)/2 이고 빅오표기법에 의해 O(N^2)이다. 

즉, 굉장히 비효율적인 정렬 알고리즘임을 알 수 있다.