[Sort] 선택정렬 - Selection Sort

무작위로 데이터들이 있을 때, 가장 작은 수를 맨 앞에 있는 것과 바꾸고 나머지 것들에 대해 또 다시 같은 과정을 반복

가장 작은 것은 맨 앞으로!

시간복잡도

for 문을 두번 돌면서 n개의 위치에 대해 제일 작은 것을 찾기 위해 n, n-1, n-2 ... 1번 탐색을 진행한다. 

n(n-1)/2로 O(n^2)의 시간복잡도를 가진다

import sys
input = sys.stdin.readline
INF = int(1e9)

arr = [4, 2, 6, 1, 9, 23, 45, 21, 28, 19]

def selectSort(arr):
    
    for i in range(0, len(arr)-1):
        min_val = INF
        min_idx = -1
        for j in range(i, len(arr)):
            if min_val > arr[j]:
                min_val = arr[j]
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

selectSort(arr)
print(arr)

 

개선된 코드

import sys
input = sys.stdin.readline

arr = [4, 2, 6, 1, 9, 23, 45, 21, 28, 19]

def selectSort(arr):
    
    for i in range(0, len(arr)-1):
        min_index = i #가장 작은 원소가 들어갈 자리의 idx
        for j in range(i+1, len(arr)):
            if arr[min_index] > arr[j]:
                min_index = j
                
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

selectSort(arr)
print(arr)