[Python] 정렬 알고리즘(2)-선택정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.

선택 정렬 동작 예시

선택 정렬 소스코드(Python)

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

for i in range(len(arr)): 
	min_index = i # 가장 작은 원소의 인덱스 
	for j in range(i + 1, len(arr)): 
		if arr[min_index] > arr[j]: 
			min_index = j 
	arr[i], arr[min_index] = arr[min_index], arr[i] # 스와프 

print(arr)

선택 정렬의 시간 복잡도

• 선택 정렬은 n번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.
• 구현방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.
  • N + (N-1) + (N-2) + ..... + 2
• 이는 (N² + N - 2) / 2로 표현 가능 --> 빅오 표기법 O(N²) 이라고 작성합니다.