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

선택 정렬(Selection Sort)

출처: https://visualgo.net/en

선택 정렬은 배열을 순회 하면서 현재 값보다 작은 값을 찾는 구조다. 위 이미지에서 8에서 시작하여 더 작은 값이 있는지 찾는다. 3이 가장 작으므로 0번 인덱스에 3이 온다. 이때 작은 값들이 오름차순으로 적재되는 것을 생각해야한다. 따라서 2회차부터는 1번 인덱스에서 시작한다.

 

이제 1번 인덱스인 41에서 순회를 시작한다. 바로 다음 숫자인 21이 더 작으므로 최소값을 담는 임시 변수는 21을 담는다. 다음으로 21과 3을 비교한다. 3이 더 작으므로 임시 변수는 3으로 교체한다. 그 뒤에는 3보다 작은 값이 없으므로 41의 자리인 1번 인덱스는 3으로 교체된다.

 

#Selection Sort
def selection_Sort(array):
    for a in range(len(array) - 1):
        min = a
        for b in range(a + 1, len(array)):
            if array[b] < array[min]:
                min = b
        array[min], array[a] = array[a], array[min]
    
    return array


#Test Code
import random
array = random.sample(range(100), 10)

print(array)
print(selection_Sort(array))