[알고리즘] 선택정렬(Selection Sort) (Python)

1. 기본 원리

• 전부를 한번 훑을 때마다 최솟값을 구한 뒤, 맨 앞의 데이터와 swap 해주는 방식

 

2. 코드 구현 전 생각정리

• n번 훑을 때마다 n개의 데이터들이 앞에서부터 fix되네?
• 반복문을 짤 때 이 부분을 생각하며 짜야겠네?

 

3. 코드 구현

def selection(input):
    for i in range(len(input)):
        min_idx = i 
        for j in range(i,len(input)):
            if input[j]<input[min_idx]:
                min_idx = j
        #min값을 가지는 index를 구한 뒤에는 swap
        input[i], input[min_idx] = input[min_idx], input[i]
        
    return input

 

4. 시간 복잡도

• 이중 for문이 있으므로 O(n^2)