선택 정렬은 뭐야?

개념

선택 정렬은 배열 A[1... n]에서 가장 작은 원소를 찾아 배열의 앞자리에 있는 A[i]와 바꾸는 것으로 원소를 넣을 위치는 결정된 상태에서 넣을 원소를 선택하는 것 알고리즘입니다.

구현 방법

오름차순을 기준으로 본 선택 정렬의 구현 방법은 다음과 같습니다.

1. 배열을 순환하며 가장 작은 원소의 인덱스를 선택한다.
2. 1의 결과를 정렬되지 않은 배열의 맨 앞 값과 교환한다.
3. 배열의 길이 -1만큼 1을 반복한다.

파이썬 구현 코드

def selection_sort(array):
    for i in range(len(array) - 1):  # 1.
        min_index = i
        for j in range(i + 1, len(array)):
            if array[j] < array[min_index]:
                min_index = j  # 2.
        array[i], array[min_index] = array[min_index], array[i]  # 3.
    return array

1. 다음 원소를 넣을 위치 인덱스를 순환한다.
2. 원소들을 비교하며 최소 원소가 저장된 인덱스를 계산한다.
3. 1의 결과와 2의 결과 인덱스의 원소를 교환한다.

그림으로 보는 선택 정렬

1번의 순환동안 값이 정렬되는 과정

위 그림은 한번의 순환 동안 값이 정렬되는 과정을 그린 것입니다. 빨간색은 현재 가장 작은 값의 원소를 나타내고, 파란색은 비교를 위해 선택된 원소를 나타냅니다. 주어진 배열에서 1이 가장 작은 값이므로 1과 정렬되지 않은 원소 중 가장 앞의 원소인 5와 자리를 교환하게 됩니다.

전체 정렬 과정

위의 그림은 전체 배열이 정렬되는 과정을 보인 것입니다. 빨간색 부분은 정렬된 원소들을 나타낸 것입니다. 버블 정렬과 유사하게 한번의 순환에 정렬된 배열의 값이 하나씩 증가되고 있는 것을 확인할 수 있습니다.

시간 복잡도

선택 정렬의 시간 복잡도는 평균, 최선, 최악의 경우 모두 O(n^2)입니다. 원소의 개수가 n개인 배열이 있다고 가정하였을 때 1️⃣의 경우 순환을 마지막 원소를 제외한 n-1번 진행합니다. 2️⃣는 부분 배열의 최솟값을 찾는 연산으로 배열의 크기에 비례하여 연산 횟수가 늘어납니다. (k개의 원소 중 가장 작은 값을 찾기 위해서는 k-1번의 비교 연산이 필요하다)

 

따라서 주어진 배열을 i번 순환할 때마다 n-i의 비교 연산이 수행됩니다. 그러므로 비교 연산의 총합은 (n-1) + (n-2) + (n-3) + (n-4) + ... + 2 + 1 = n(n-1)/2, 즉 시간 복잡도가 O(n^2)가 됩니다.

결론

선택 정렬은 버블 정렬에 비해 교환 연산 횟수를 n번으로 줄여 효율성 측면에서 버블 정렬에 비해 더 좋지만 여전히 시간 복잡도가 평균, 최선, 최악의 경우에 O(n^2)이므로 개선의 여지가 있습니다. 

 

[참고 자료 및 깃허브 코드]

쉽게 배우는 알고리즘, 문병로, 한빛아카데미, 2018-01-20

깃허브(Github) - 선택 정렬 알고리즘 구현