쉽게 설명한 선택 정렬 알고리즘
1) 최솟값의 위치를 찾아주는 find_min_idx 함수 작성
2) 최솟값의 위치를 사용해 pop함수를 사용하여 해당 최솟값을 value 라는 변수에 저장
3) result라는 빈 리스트에 append 함수를 사용하여 value 값을 순서대로 붙여줌
일반적인 선택 정렬 알고리즘
중첩 반복문이라 헷갈릴 수도 있는데 원리는 간단하다.
i는 0부터 리스트의 맨 마지막에서 두번째까지
j는 1부터 리스트의 맨 마지막까지
a[i]와 a[j]를 비교해서 만약 a[j]가 더 작으면 j를 min_idx에 저장
for 문이 끝나면 a[i]자리에 a[min_idx]를, a[min_dix]자리에 a[i]를 대입
- a = [1,4,5,2,3]
n = len(a) = 5
for i in range(0,4):
min_idx = i
for j in range(1,5):
if a[j] < a[min_idx]
min_idx = j
a[i],a[min_idx] = a[min_idx],a[i]
i = 0 이면,
min_idx = 0
j = 1
a[1] < a[0] # a[1] == 4, a[0] == 1, 4<1 성립 x
j = 2
a[2] < a[0] # a[2] == 5, a[0] == 1, 5<1 성립 x
j = 3
a[3] < a[0] # a[3] == 2, a[0] == 1, 2<1 성립 x
j = 4
a[4] < a[0] # a[4] == 3, a[0] == 1, 3<1 성립 x
a[0],a[0] = a[0],a[0] 이므로 a에 아무 변화 x
a = [1,4,5,2,3]
i = 1 이면,
min_idx = 1
j = 2
a[2] < a[1] # a[2] == 5, a[1] == 4, 5<4 성립 x
j = 3
a[3] < a[1] # a[3] == 2, a[1] == 4, 2<4 성립 o
min_idx = 3 실행
j = 4
a[4] < a[3] # a[4] == 3, a[3] == 2, 3<2 성립 x
a[1],a[3] = a[3],a[1] 이므로 a[1]인 4와 a[3]인 2가 교환
a = [1,2,5,4,3]
i = 2 이면,
min_idx = 2
j = 3
a[3] < a[2] # a[3] == 4, a[2] == 5, 4<5 성립 o
min_idx = 3 실행
j = 4
a[4] < a[3] # a[4] == 3, a[3] == 4, 3<4 성립 O
min_idx = 4실행
a[2],a[4] = a[4],a[2] 이므로 a[1]인 3와 a[2]인 5가 교환
a = [1,2,3,4,5]
i = 3이면,
min_idx = 3
j = 4
a[4] < a[3] # a[4] == 5, a[3] == 4 5<4 성립x
a[3],a[3] = a[3],a[3] 이므로 a에 아무 변화 x
a = [1,2,3,4,5]
