[알고리즘 공부] 2. Selection Sort (선택 정렬)

Selection Sort

버블 정렬과 비해도 크게 어렵지 않은 쉬운 정렬 중 하나인 Selection Sort(선택 정렬)입니다.

 

선택 정렬은 수열을 배회하다가 가장 작은 수를 찾아 맨 앞으로 내보내고 그 다음 숫자부터 반복하는 쉬운 정렬 입니다.

 

버블 정렬과 마찬가지로 구현의 간단함을 대가로 시간 복잡도를 잃었습니다. 

 

선택 정렬의 시간 복잡도는 O(n^2)으로 버블 정렬과 동일합니다.

 

크게 어려운 것이 없으니 마찬가지로 파이썬 구현으로 넘어가겠습니다.

---

input = [14,54,5,2,1,36,324,34,213,6,7,4]

def SelectionSort(input):
    
    length = len(input)
    
    
    # 한바퀴 돌때 마다 시작 숫자는 한칸씩 뒤로   
    for x in range(length):         
        for y in range(x, length):
        
        	# 가장 작은 숫자 idx 저장 
            if input[y] <= input[idx]:
                idx = y
        
        # 한바퀴 돌고 나면 가장 작은 숫자와 맨 앞자리 숫자 위치 변경
        input[x], input[idx] = input[idx], input[x]
    return input

print(SelectionSort(input))