선택정렬(Selection sort)

정렬(sort)

정렬이란 순서가 없는 원소(record) 들을 일정한 순서대로(오름차순 , 내림차순)원소들을 재배열 하는것을 정렬이라고 한다. 효율적인 정렬을 사용하면 자신이 원하는 원소를 빠르게 얻을수 있다.

기본적인 정렬 알고리즘

1. 선택정렬
2. 삽입정렬
3. 버블정렬
4. 합병정렬
5. 퀵정렬

여기에서는 우선 선택정렬을 알아보자

선택정렬(Selection sort)

선택정렬은 제자리 정렬 알고리즘의 한가지이다. 주어진 원소들을 처음부터 끝까지 차례대로 비교하여 가장 작은것이 첫번째 , 나머지 원소들을 다시 끝까지 비교하여 가장 작은것이 두번째. 이것을 처음부터 끝까지 하는것을 선택정렬이라고 한다.

선택 정렬

선택정렬 알고리즘은 (n-1)(n-2)(n-3)……1 개씩 비교를 한다. 이것을 시간복잡도로 계산하면 Θ(n2)의 시간복잡도를 가진다.

아래는 선택정렬을 파이썬으로 구현한 코드이다.

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