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

선택 정렬은 정렬되지 않은 영역에서 최솟값을 선택한 뒤, 정렬되지 않은 영역의 첫번째 요소와 바꾸고 고정시키는 과정을 반복하는 정렬 방식이다.

물론 최댓값을 이용한 정렬도 가능하다. 

시간 복잡도는 버블 정렬과 마찬가지로 O(n**2)이다.

 

 

 

아래의 배열에 대한 오름차순 선택 정렬을 실시해보자.

 

 

먼저, 전체 구간에서 가장 작은 요소를 선택한다. 1이 선택될 것이다.

 

 

이렇게 선택된 1을 가장 왼쪽에 위치한 2와 서로 맞바꾼 뒤, 고정시킨다.

다시 정렬되지 않은 영역에서 가장 작은 요소를 선택한다.

 

 

1은 이미 고정되었으므로 2가 최솟값이다.

순서가 고정 되지 않은 배열의 제일 왼쪽에 위치한 요소와 서로 자리를 바꾸어준다.

 

 

2 역시 앞으로 위치를 바꾸지 않을 것이다. 위치가 고정된 것이다.

 

 

같은 과정을 계속 반복하면 된다. 고정되지 않은 배열의 최솟값인 3을 선택하여 제일 왼쪽의 요소와 자리바꿈을 한다.

 

 

마지막으로 남은 두 요소의 위치까지 바꿔주면 오름차순으로 정렬이 된 것을 확인할 수 있다.

 

 

 

선택 정렬은 버블 정렬과 마찬가지로 한 번 시행을 반복할 때마다 요소들이 고정된, 즉 정렬이 완료된 영역이 하나씩 늘어나는 것을 확인할 수 있다.

 

 

 

선택 정렬을 파이썬으로 구현하자면, 아래와 같이 표현할 수 있다.

 

def SelectionSort(arr):
	for i in range(len(arr)-1):
    		j = arr.index(min(arr[i:])
        	arr[j], arr[i] = arr[i], arr[j]