[Algorithm] Selection Sort(선택 정렬)

Selection Sort

선택 정렬은 정한 자리에 들어갈 값을 찾아 넣어주는 방식으로 정렬을 진행한다.
불안정 정렬에 속한다.

구현 방법

정해진 배열 중에 가장 작은 값을 찾아서 0번 자리에 넣는 것을 시작으로 1,2,..n 번까지 진행한다. 한 사이클이 돌 때마다 1자리는 정해지면서 진행된다.

구현(Python) - 1

가장 작은 값을 반복문을 돌면서 찾는 방법

def selectionsort(test):
    for i in range(len(test)):
        min_value = i
        for j in range(i+1, len(test)):
            if test[j] < test[min_value]:
                min_value = j
        test[i], test[min_value] = test[min_value], test[i]
    print(test)

구현(Python) -2

python에서 제공하는 min 함수를 사용하는 방법

def selectionsort2(test):
    for i in range(len(test)):
        min_value = min(test[i:])
        min_index = test.index(min_value)
        test[i], test[min_index] = test[min_index], test[i]
    print(test)

결과

import time
if __name__ == '__main__':
    start = time.time()  # 시작 시간 저장
    test = [4,6,2,8,9,7,1]
    selectionsort(test)
    print("time1 :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간

    start = time.time()  # 시작 시간 저장
    test = [4, 6, 2, 8, 9, 7, 1]
    selectionsort2(test)
    print("time2 :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간

time1 : 3.62396240234375e-05
time2 : 1.1920928955078125e-05

시간복잡도

데이터의 개수가 n개일 때, (n-1)+(n-2)+...+1 의 시간이 소요되므로 O(n^2)의 시간복잡도가 나온다.

공간복잡도

배열 내에서 자리가 변경되면서 진행하는 알고리즘이므로 O(n)의 공간복잡도가 나온다.