[알고리즘][파이썬/Python] 선택 정렬 (Selection Sort)

정의

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식의 정렬 알고리즘

 

동작 방식

1. 반복 시작 시, 시작 index를 최소값의 index로 지정

2. 시작 위치 이후에 있는 모든 원소를 한 번씩 방문하며 최소값과 비교

3. 더 작은 값이 발견될 경우, 해당 값의 index를 최소값의 index로 업데이트

4. 반복이 끝난 후 시작 index와 최소값 index가 다를 경우, 두 index에 위치한 원소들을 교환

5. 위 과정을 반복하면서 정렬

 

메모리 사용 공간

n개의 원소에 대하여 n개의 메모리 사용

 

연산 시간

1. 최선의 경우 (Best Case) : 자료가 이미 정렬되어 있는 경우

- 비교횟수 : 처음 비교할 때 (n-1)회, 두 번째 비교할 때 (n-2)회, ..., i번째 비교할 때 (n-i)회, ..., (n-1)번째 비교할 때 1회 = n(n-1) / 2

- 자리교환횟수 : 자리교환이 발생하지 않는다.

- 총 소요 시간 : n(n-1) / 2

 

2. 최악의 경우 (Worst Case) : 정렬된 자료에서 최소값만 맨 뒤에 위치한 경우 (ex. [2, 3, 4, 5, 1])

- 비교횟수 : (n-1) + (n-2) + (n-3) + ... + (n-i) + ... + 1 번 = n(n-1) / 2

- 자리교환횟수 : 모든 i번째 실행 시 1번 교환하므로, n-1

- 총 소요 시간 : n(n-1) / 2 + (n-1)

 

∴ 시간 복잡도 T(n) = O(N^2)

 

소스 코드

# 선택 정렬 (Selection Sort)

# 선택 정렬 - 오름차순 (Selection Sort - Ascending)
def selectionSort_ASC(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 선택 정렬 - 내림차순 (Selection Sort - Descending)
def selectionSort_DESC(arr):
    n = len(arr)
    for i in range(n-1):
        max_idx = i
        for j in range(i+1, n):
            if arr[j] > arr[max_idx]:
                max_idx = j
        if max_idx != i:
            arr[i], arr[max_idx] = arr[max_idx], arr[i]
    return arr
            
# 난수를 생성하여 test해보기 (Test by random number) 
from random import randint

lst = [randint(1, 101) for i in range(5)]
print('Selection Sort(ASC) :', lst, end=' '); print('->', selectionSort_ASC(lst))
# Selection Sort(ASC) : [26, 71, 90, 37, 3] -> [3, 26, 37, 71, 90]

lst = [randint(1, 101) for i in range(5)]
print('Selection Sort(DESC) :', lst, end=' '); print('->', selectionSort_DESC(lst))
# Selection Sort(DESC) : [79, 44, 2, 50, 56] -> [79, 56, 50, 44, 2]

최악의 경우를 생각해봤을 때, 선택 정렬은 버블 정렬보다는 아주 약간 효율적일 수는 있겠다. 그래 봤자 결국 시간 복잡도는 O(N^2)이므로, 선택 정렬 또한 효율이 좋지 않은 정렬에 속한다.