알고리즘)정렬(3/4)-선택정렬(selection)

선택정렬은 데이터에서 작은 수 오름차순으로 찾아서(선택해서) 순차적으로 데이터를 넣어주는 것입니다.

이미 array에 데이터가 있는 상황이기에 앞서 있는 요소와 자리를 바꿔준다고 생각하면 됩니다.

 

알고리즘을 구현할때 필요한 것

1. 현재 위치를 알 수 있는 것(데이터를 바꿔 넣을 자리를 기억하고 있는 것)

2. 작은 수의 인덱스를 찾을 것 

3. 작은 수의 데이터를 바꿔 넣을 자리에 넣어주는 것 

 

def selectionSort(data):
    for i in range(len(data)):
        lowest = i #바꿀 자리를 lowest로 초기화 
        for j in range(i,len(data)):
            if data[lowest] > data[j] :
                lowest = j #더 작은 데이터의 인덱스 번호로 바꿔줌 
        data[lowest], data[i] = data[i], data[lowest]
    return data

잘 바뀌는 것을 확인할 수 있습니다. 

 

선택정렬도 for문을 두번 쓰기 때문에 시간 복잡도가 O(n^2)임을 알 수 있습니다.