선택 정렬 알고리즘

선택 정렬

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

동작 예시

[Step 0] 처리되지 않은 데이터 중 가장 작은 0을 선택해 가장 앞인 7과 바꿉니다.

[Step 1] 처리되지 않은 데이터 중 가장 작은 1을 선택해 가장 앞인 5와 바꿉니다.

[Step 2] 처리되지 않은 데이터 중 가장 작은 2을 선택해 가장 앞인 9와 바꿉니다.

[Step 3] 처리되지 않은 데이터 중 가장 작은 3을 선택해 가장 앞인 7과 바꿉니다.

이러한 과정을 반복하면 다음과 같이 정렬이 완료됩니다.

소스코드

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

for i in range(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]

시간 복잡도

선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.

전체 연산 횟수는 N + (N-1) + (N-2) + ... + 2와 같고 이는 빅오 표기법에 따라 O(N^2)라고 작성합니다. 1