[알고리즘 공부] 선택정렬

오늘의 알고리즘은 선택정렬입니다.선택정렬은 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하여 정렬하는 정렬 알고리즘으로 버블정렬과 함께 가장 기초적인 알고리즘에 속합니다.

 

선택정렬 시간복잡도

선택정렬은 2중 반복문을 이용하기 때문에 O(n^2)의 시간복잡도를 가지고 있습니다. 즉, 버블정렬처럼 엄청나게 느린 정렬 알고리즘이라는 이야기입니다. 내장 정렬보다 훨씬 느리고, 그렇기 때문에 실무에서는 거의 쓰일 일이 없습니다.

 

선택정렬 코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
	min_idx = i #가장 작은 원소의 인덱스
	for j in range(i + 1, len(array)):
		if array[min_idx] > array[j]:
			min_idx = j
            array[i], array[min_idx] = array[min_idx], array[i] #파이썬식 스왑
print(array)

출력결과는 당연히 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 가 될 것입니다.