정렬 알고리즘 (1) - 선택 정렬

선택 정렬 : 데이터가 무작위로 여러 개 있을 때 그 중 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸고 이 과정을 반복하는 것

 

예를 들어 아래 그림과 같은 배열이 있다고 생각해보자. 

step1. 이 배열에서 가장 작은 데이터는 0 이다. 0을 선택하여 제일 앞에 있는 7과 바꾼다. 

 

step2. 핑크색으로 색칠된 데이터는 이미 정렬된 데이터를 의미한다. 그 데이터를 제외하고 다시 가장 작은 데이터를 선택한다  (여기서는 1) 그리고 가장 앞에 있는 데이터 5와 맞바꾼다.

 

 

이러한 과정을 반복하면 

 

정렬된 배열을 얻을 수 있다.

이 과정을 코드로 작성해보면 아래와 같다. 

 

array = [7,5,9,0,3,2,6,2,4]
for i in range(len(array)):
	min_index = i #가장 작은 데이터의 인덱스
    for j in range(i+1,len(array)): #정렬 안된 부분에서 가장 작은 데이터 찾기
    	if(array[j] < array[min_index]): #더 작은 데이터가 있다면
        	min_index = j #업데이트
    array[i], array[min_index] = array[min_index], array[i] #데이터 swap
print(array)

 

 

선택 정렬의 시간 복잡도는 O(n2)이다. 반복문이 두번 사용 되었기 때문이다. 가장 작은 데이터와 맨앞의 데이터를 바꾸는 반복문 하나와 가장 작은 데이터를 찾기 위한 반복문 하나.