선택정렬은 각 값들을 하나씩 탐색 한 후 가장 작은 숫자를 찾아 맨 앞 인덱스에 넣고, 두 번째로 작은 값을 찾아 첫번 쨰 인덱스에 넣고 세 번째로 작은 값을 찾아 두 번째 인덱스에 넣는 식으로 정렬이 끝날 때 까지 위의 과정을 반복하는 방법이다. 버블 정렬이 가장 끝의 인덱스에 큰 숫자가 정렬되는 것과 달리 선택 정렬은 앞 인덱스에 작은 숫자 순서대로 정렬이된다. 이또한 두 개의 for문을 돌아야 하므로 O(N^2)만큼의 복잡도를 가진다.
input = [4, 6, 2, 9, 1]
def selection_sort(array):
n = len(array)
for i in range(n - 1):
# 최솟값 저장(인덱스에)
min_idx = i
for j in range(n - i):
if array[i + j] < array[min_idx]:
min_idx = i + j
array[i],array[min_idx] = array[min_idx],array[i]
return
selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!첫 번째 for문에서 배열의 길이에 -1을 해 준 이유는 모든 값이 정렬이 되었을 때 맨 뒤의 값 또한 자동으로 정렬되기 때문에 맨 뒤의 값은 탐색하지 않아도 되기 때문이다.
두 번째 for문은 첫 번째 for문이 하나씩 진행 될 때 마다 작은 숫자가 순서대로 정렬 되므로, i값을 뺀 횟수만큼 돌아야한다. 그 후 가장 작은 값을 탐색 해 나가야 하므로 가장 작은 최솟값은 i번쨰 인덱스로 설정해 놓고 만약 그 값보다 지금 탐색하는 값이 더 작다면 인덱스에 그 값을 넣어 각 값들을 바꿔준 후 정렬 해 나가야 한다.