[알고리즘 이론] 선택 정렬 (Selection Sort)

• 선택 정렬: 다음과 같은 순서를 반복하며 정렬하는 알고리즘
  1. 주어진 데이터들 중, 최솟값을 찾음
  2. 해당 최솟값을 데이터 맨 앞에 위치한 값과 교체
  3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복

 

출처 : https://en.wikipedia.org/wiki/Selection_sort

 

""" 선택 정렬 구현 코드 """

def selection_sort(data):
	for stand in range(len(data) - 1):
		lowest = stand
		for i in range(stand+1, len(data)):
			if data[lowest] > data[i]:
				lowest = i
		data[lowest], data[stand] = data[stand], data[lowest]
	return data

 

- 반복문이 두 개 이므로 시간 복잡도 : O(n^2)