선택 정렬 '가장 작은 것을 선택'

데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고,

그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸 는 과정을 반복하면 어떨까?

 

가장 원시적인 방법으로 매번 "가장 작은 것을 선택" 한다는 의미에서 선택 정렬 알고리즘이라 한다.

 

선택정렬 설명

step0 ) 초기 단계에서는 모든 데이터가 정렬 되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다.

따라서 '0'을 선택해 맨 앞에 있는 데이터 '7'과 바꾼다.

7 5 9 0 3 1 6 2 4 8

 

step1) 이제 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 '1'을 선택해서 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '5'와 바꾼다.

0 5 9 7 3 1 6 2 4 8 

 

step2) 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '2'를 선택한다.

이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '9'와 바꾼다.

0 1 9 7 3 5 6 2 4 8

 

이 과정을 반복하면 

0 1 2 3 4 5 6 7 8 9 순으로 배열을 할 수 있다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프

print(array)

 

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

스와프 특정 리스트가 주어졌을 때 두변수의 위치를 변경하는 작업을 의미한다.