[Sort] Selection Sort (선택 정렬)

주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식(오름차순인 경우)

 

정의

• 자기자신 보다 오른쪽에 놓여있는 값중 최솟값과 자리를 바꾼다.
• 결과적으로 최소값~최댓값으로 정렬이 가능하다.

 

설명

• 버블소트와 굉장히 유사한 방법.
• 버블 소트는 바로 다음 인덱스의 값과 교환을 하고, 선택정렬을 최소값과 교환을 한다.
• 교환 대상만 다를뿐 탐색 횟수는 동일

 

시간복잡도

• O(n^2)

 

구현

def SelectionSort(a):
	for i in range(0, len(a)-1): # 마지막 원소는 앞선 수행에서 자동 정렬되서 정렬X
		min_idx = i # 자기자신을 최소값이라고 가정 (초기화)
		for j in range(i+1, len(a)): # 내 다음에 나오는 원소들과 비교
			if a[min_idx] > a[j]: # 최소값보다 더 작은 값이 나오면
				min_idx = j # 그때의 인덱스를 최소인덱스로 지정
		a[i], a[min_idx] = a[min_idx], a[i] # 반복문 종료후, 진짜 최소값이 정해지면 교환