2. 선택 정렬

선택정렬은 정렬 알고리즘의 하나로 리스트 자료형에서 적은 비용을 부과하는 특징을 가지고 있다.

 

1. 주어진 리스트에서 최소값을 찾는다.

2. 리스트의 맨 첫번째를 n이라고 하고, 처음에는 n의 위치로 최소값을 이동한다.

3. 다시 최소값을 찾아 n+1 위치로 이동한다.

4. 정렬될 때까지 위 3번 항목을 반복한다.

 

 

리스트가 [ 5,4,2,1,0,3 ] 일 경우,

 

pass	table	최소값
0	[ 5,4,2,1,0,3 ]	0
1	[ 0,5,4,2,1,3 ]	1
2	[ 0,1,5,4,2,3 ]	2
3	[ 0,1,2,5,4,3 ]	3
4	[ 0,1,2,3,5,4 ]	4
5	[ 0,1,2,3,4,5 ]	5

 

『시간 복잡도』

 

O(n^2) 이며, 모든 수를 swap 할 경우이다.

Ω(n^2) 이며, swap의 수가 0번 일 경우이다.

 

이유는 모든 테이블을 한번씩 훑어 행동을 취하기 때문이다.

즉 swap이 0이어도, 각 자리수를 제한,검사하는 pass의 수는 같기 때문에시간복잡도의 최상, 최악이 같다.

 

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

파이썬에서의 구현

 

코드 출처: https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

선택 정렬 - 위키백과, 우리 모두의 백과사전