선택 정렬

매번 가장 작은 것을 선택하여 차례대로 바꿈

 

[과정]

 

데이터의 개수 = 6

현재 정렬되지 않은 데이터 중 가장 작은 데이터 = 회색

이미 정렬된 데이터 = 하늘색

 

초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로, 가장 작은 데이터를 선택한다.

가장 작은 데이터 '0'을 선택해 맨 앞에 있는 데이터 '5'와 자리를 바꾼다.

 

정렬되어 있지 않은 데이터 중 가장 작은 데이터 '1'을 선택한다.

'1'이 현재 있는 자리는 정렬되어 있지 않은 데이터 중 가장 앞자리이므로 그대로 둔다.

 

정렬되어 있지 않은 데이터 중 가장 작은 데이터 '2'를 선택한다.

 

정렬되어 있지 않은 데이터 중 가장 앞자리에 있는 '4'의 자리에 '2'를 둔다.

그 후 정렬되어 있지 않은 데이터 중 가장 작은 데이터 '3'을 선택한다.

 

정렬되어 있지 않은 데이터 중 가장 앞자리에 있는 '5'의 자리에 '3'를 둔다.

그 후 정렬되어 있지 않은 데이터 중 가장 작은 데이터 '4'을 선택한다.

 

'4'의 위치가 이미 정렬되어 있지 않은 데이터 중 가장 앞에 있으므로 그 자리에 둔다.

마지막 데이터는 가만히 두어도 이미 정렬된 상태이다.

따라서 이 단계에서 정렬을 마칠 수 있다.

 

[결과]

선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 '데이터의 개수 - 1'번 반복하면 정렬이 완료된다.

 

 

[코드]

data = [5, 1, 4, 0, 2, 3]

for i in range(len(data)):
    min_index = i
    for j in range(i + 1, len(data)):
        if data[min_index] > data[j]:
            min_index = j
    data[i], data[min_index] = data[min_index], data[i]  # swap

print(data)

 

 

[시간 복잡도]

N(데이터의 개수)-1번 만큼 가장 작은 수를 찾아 앞으로 보내야함.

매번 가장 작은 수를 찾기 위해 비교연산 필요

-> N + (N-1) + (N-2) + ... + 2 ≒ N x (N+1) / 2 = (N^2 + N) /2

O(N^2)