#02 - 선택 정렬(Selection Sort)

매번 루프마다 가장 작은 최솟값을 선택해서 맨 앞부터 하나씩 채우는 알고리즘

https://gyoogle.dev/blog/algorithm/Selection%20Sort.html

시간 복잡도 : 최선, 평균, 최악의 경우 시간 복잡도는O(n^2)으로 동일

공간 복잡도 : 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.

 

def selectionsort(arr):
    n = len(arr)
    for i in range(n-1):
        min_index = i
        for j in range(i+1,n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

수행시간 비교

 

확실히 교환작업에서 시간을 단축해서 bubble sort보단 빠른 것 같다.

 

그래도 여전히 비효율적이다 n^2

불안정 정렬(Unstable Sort) 이다.