선택 정렬(Selection Sort)

주어진 데이터 중 최소값을 찾아 맨 앞에 위치한 데이터와 바꾸는 정렬 알고리즘
시간 복잡도 : O(N^2)

예제

첫 번째 데이터 1은 이미 최소값이기 때문에 정렬됨
맨 앞 데이터는 10, 최소값은 2 👉 swap
맨 앞 데이터는 5, 최소값은 3 👉 swap
맨 앞 데이터는 8, 최소값은 4 👉 swap
맨 앞 데이터는 7, 최소값은 5 👉 swap
맨 앞 데이터는 6, 최소값도 6 👉 유지
맨 앞 데이터는 8, 최소값은 7 👉 swap
맨 앞 데이터는 8, 최소값도 8 👉 유지
맨 앞 데이터는 10, 최소값은 9 👉 swap
맨 앞 데이터는 10, 최소값은 10 👉 유지

구현

github link

def selection_sort(data):
    for i in range(len(data)):
        min_idx = i
        for j in range(i+1, len(data)):
            if (data[min_idx] > data[j]):
                min_idx = j
        data[i], data[min_idx] = data[min_idx], data[i]
    return data

if __name__ == "__main__":
    data = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
    res = selection_sort2(data)
    print('res: ', res)

데이터 개수만큼 반복하면서:
첫 번째 : 0~n중 최소값을 찾아 data[0]이 더 크다면 data[0]과 swap
두 번째 : 1~n중 최소값을 찾아 data[1]이 더 크다면 data[1]과 swap
(i-1)번째 : i~n중 최소값을 찾아 data[i]이 더 크다면 data[i]과 swap

(2) 데이터 길이만큼 loop를 돌면서
(3) 일단 맨 앞의 인덱스를 가장 작은 원소의 인덱스로 설정
(4-6) 맨 앞의 요소를 제외하고 가장 작은 숫자를 찾는다
(7) 최소값과 맨 앞의 요소를 swap: C언어와 다르게 파이썬에서는 임시 저장용 변수를 사용하지 않고 두 변수의 값을 변경할 수 있다.

int a = 3;
int b = 5;

int temp = a;
a = b;
b = temp;

C언어에서 swap을 하려면 임시 저장용 변수 temp가 필요하다.

시간 복잡도

선택 정렬은 N-1만큼 가장 작은 수를 찾아 맨 앞으로 보낸다.
매번 가장 작은 수를 찾기 위해서는 비교 연산이 필요하다. 위의 구현 코드를 바탕으로 연산 횟수는 N + (N-1) + (N-2) + ... + 2로 볼 수 있다.
근사치로 표현하면 N x (N+1) / 2 이며, 빅오 표기법으로 간단히 O(N^2)으로 표현할 수 있다.
소스코드에서 이중 for문이 사용되었기 때문에 시간 복잡도가 O(N^2)이라고 판단할 수 있다. 즉, 선택 정렬은 정렬할 데이터의 개수가 100개 들어나면, 수행 시간은 10000배로 늘어난다.

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다.
또한, 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸기 때문에 비효율적이다.

References
나동빈 알고리즘 강의