[파이썬 알고리즘] 선택정렬(selection sort)이란?

선택정렬이란?

선택정렬은 아주 단순한 정렬 알고리즘입니다.
최소값을 찾은 후 맨 앞에 데이터와 교체하는 것을 반복하는 방법입니다.
당연히 정리가 끝난 인덱스 이후로 반복해야합니다. 다시 처음부터 하면 안됩니다.
내가 최소값을 선택한 후 그걸 맨 앞으로 끌어오는 작업만 하면 됩니다. 그래서 선택정렬이라고 하는게 아닌가 싶습니다.

출처: https://en.wikipedia.org/wiki/Selection_sort

 

알고리즘 구현

선택정렬은 최소값을 선택하고 지정한 리스트의 앞의 값이랑 비교를 해야합니다.
맨 앞에 있는 값과 최소값을 비교해 작으면 바꿉니다(swipping)
예를 들어, 데이터가 3개 [16,3,8]라면 처음 한 번 실행할때 [16,3,8]의 최소값인 3과 맨 앞값인 16을 앞으로 넣습니다.
따라서, [3,16,8] 이 됩니다.
두번째는 3은 완료됐으므로 [16,8]에서 최소값인 8을 선택한 후 16과 비교한 후 8이 더 작으니 [3,8,16]순으로 배열합니다.

def selection_sort(data):
    for select in range(len(data) - 1):
        lowest = select
        for index in range(select + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[select] = data[select], data[lowest]
    return data

선택 for문으로 값을 선택하고 비교 for문을 할 때 범위를 비교가 끝난 인덱스 이후로 잡아주는게 포인트입니다.

import random 

data = random.sample(range(100),10)
selection_sort(data)

파이썬 min 함수 이용

min 함수를 통해 파이썬 리스트는 최소값을 도출할 수 있습니다. 이를 이용해서 선택정렬을 보다 직관적인 접근을 할 수 있습니다. 단, while을 써야 합니다.
while로 써도 똑같은 시간복잡도를 갖기 때문에 시간이 줄진 않습니다.

def selection_sort_while(data_list):
    count = 0
    while len(data_list)>count:
        data = data_list[count:]
        minvalue = min(data)
        min_index = data_list.index(minvalue)
        comparevalue = data[0]
        comparevalue_index = data_list.index(comparevalue)
        if comparevalue>minvalue:
            data_list[comparevalue_index] = minvalue
            data_list[min_index] = comparevalue
            count +=1
        else:
            count +=1
    return data_list

print(data_list)
selection_sort_while(data_list)

for문과 while문의 실제 시간을 비교해보면 그리 차이 나지 않는 걸 볼 수 있습니다.

%timeit selection_sort_while(data_list)
%timeit selection_sort(data_list)

 

시간복잡도

for문이 두개 입니다. $ O(n^2)$ 됩니다.
실제로 n개의 데이터를 선택정렬 알고리즘으로 정렬을 실행한다면
n+(n-1)+...+1 으로 for문이 돌게 되므로 $ \frac{n(n-1)}{2} $ 가 됩니다.