알고리즘 개념 4. 선택정렬 Selection sort

 

- 제자리 정렬 알고리즘

- 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

 

순서

(1) 주어진 리스트에서 최솟값을 찾는다

(2) 그 최솟값을 맨 앞의 값과 교체한다. (pass)

(3) 맨 앞 위치를 빼고 나머지 리스트를 같은 방법으로 계속 정렬한다. 

 

걸리는 시간은?

n개의 리스트가 있다고 한다면  Θ(n2)만큼 시간이 걸린다.

* for loops 2개로 이루어짐 -> 첫번째 루프횟수 : (n-1) 두번째도 (n-1)

* 값 교환 횟수 = 3(n-1)

 

장점?

자료의 이동횟수가 미리 정해져 있다

 

단점?

안정성을 만족하지 않고, 값이 같은 속성이 있는 경우 상대적 위치가 변경될 수 있다. 

 

python example

def selectionSort(x):
	length = len(x)
	for i in range(length-1):
	    indexMin = i
		for j in range(i+1, length):
			if x[indexMin] > x[j]:
				indexMin = j
		x[i], x[indexMin] = x[indexMin], x[i]
	return x