[Algorithm] 선택 정렬

선택 정렬은 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것이다. 예제를 통해 자세한 동작 원리를 알아보자.

 

 

이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N - 1번 반복하면 정렬이 완료된다.

외부의 루프를 (N-1)번 도는 동안, 각 자리에 와야하는 최댓값을 구하기 위하여 N-1, N-2, N-3, ... , 1번의 비교연산을 수행한다. 따라서, T(n) = (n-1)+(n-2)+(n-3)+...+1 = (n-1)*n/2

시간복잡도는O(n) = n^2 이다.

 

파이썬으로 소스코드를 작성해보면 다음과 같다.

 

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]  # swap
print(array)