선택정렬 알고리즘

선택정렬 알고리즘(selection sort) 

 데이터가 무작위로 나열 되어 있을때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정이다. 

 

이해를 돕기 위해서 다음과 같이 나타내 보았다.

 

step 0

초기에는 모든 데이터가 정렬 되어 있지 안흠으로, 전체 중에서 가장 작은 데이터를 선택한다. 그럼으로, '0'과 맨 앞 '7'을 바꾼다.

7 5 9 0 3 1 6 2 4 8 --> 0 5 9 7 3 1 6 2 4 8  

 

step 1

이제 정렬된 첫번째 수를 제외하고 이후 데이터 중에서 가장 작은 데이터인 '1'을 선택해서 처리되지 않은 다음 수 '5'와 바꿔준다.

0 5 9 7 3 1 6 2 4 8 --> 0 1 9 7 3 5 6 2 4 8

 

step 2

다음은 '9'와 그 다음 가장 작은 수인 '2'와 바꿔준다

0 1 9 7 3 5 6 2 4 8 --> 0 1 2 7 3 5 6 9 4 8

 

이런 순서로 정렬해 나가면 결국 마지막 전에는

 

step 8

0 1 2 3 4 5 6 7 9 8 이렇게 남을 것이고  

 

마지막 9와 8이 바뀜으로서

 

step 9

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)

 출력 값은 정상적으로