728x90
[선택정렬]
전체에서 최솟값을 "선택" 하는 것
말 그대로 선택해서 정렬한다고 생각하면 됨
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6과 2와 9와 1을 차례차례 비교합니다.
그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다!
[1, 6, 2, 9, 4]
이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다.
가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요
그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다.
2단계 : [1, 6, 2, 9, 4]
6과 2와 9와 4를 차례차례 비교합니다.
그 중 가장 작은 2와 두번째 앞 자리인 6을 교체합니다
[1, 2, 6, 9, 4]
3단계 : [1, 2, 6, 9, 4]
6과 9와 4를 차례차례 비교합니다.
그 중 가장 작은 4와 세번째 앞 자리인 6을 교체합니다
[1, 2, 4, 9, 6]
4단계 : [1, 2, 4, 9, 6]
9와 6을 비교합니다!
그 중 가장 작은 6과 네번째 앞 자리인 9을 교체합니다
[1, 2, 4, 6, 9]
[문제]
다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 선택 정렬을 이용해서 정렬하시오.
1번째 : [4, 6, 2, 9, 1]
4, 6, 2, 9, 1 중 최솟값 찾기
2번째 : [1, 6, 2, 9, 4]
6, 2, 9, 4 중 최솟값 찾기
3번째 : [1, 2, 6, 9, 4]
6, 9, 4 중 최솟값 찾기
4번째 : [1, 2, 4, 9, 6]
9, 6 중 최솟값 찾기
5번째 : 이미 정렬되었기 때문에 할 필요 없음!!!
배열의 크기만큼 반복했다가, 앞에서부터 1개씩 줄어들면서 반복하게됨
버블 정렬하고 다른 건 "최솟값"을 찾아 변경하는 것
min_index 라는 변수를 통해 각각의 인덱스들과 비교
내부의 반복문이 끝나면 최소 값의 인덱스와 i의 값들을 교체
풀이)
input = [4, 6, 2, 9, 1]
# 시간복잡도: O(N^2)
def selection_sort(array):
n = len(array)
for i in range(n - 1):
min_index = i
for j in range(n - i):
if array[i + j] < array[min_index]:
min_index = i + j
array[i], array[min_index] = array[min_index], array[i]
return
selection_sort(input)
print(input) # [1, 2, 4, 6, 9]
나의 풀이)
input = [4, 6, 2, 9, 1]
def selection_sort(array):
for current_index in range(len(array)-1):
min_number = array[current_index+1]
min_index = current_index+1
for i in range(current_index+1, len(array)):
if array[i] < min_number:
min_number = array[i]
min_index = i
array[current_index], array[min_index] = array[min_index], array[current_index]
return
selection_sort(input)
print(input) # [1, 2, 4, 6, 9]
맨 왼쪽부터 보면 최솟값이 찾아지면서 쌓아지는구나!! 라고 생각하면 됨