8선택 정렬
◼︎ 8-1 선택 정렬 과정
일반적인 선택 정렬은 처리할 대상 범위에서 최솟값을 찾아 그 값과 범위의 맨 앞에 있는 값을 서로 바꾸는 과정을 반복합니다. 이 과정이 한 번 끝날 때마다 범위 안의 맨 앞에 있는 값은 정렬이 끝난 것이므로 정렬 대상 범위에서 제외합니다.
이해를 돕기 위해 이미 정렬이 끝난 부분과 앞으로 처리될 대상 범위 사이에 세로 선(|)을 넣어 구분하였습니다.
| 2 4 5 1 3 ← 시작, 전체 리스트인 2, 4, 5, 1, 3을 대상으로 최솟값을 찾습니다.
| 1 4 5 2 3 ← 최솟값 1을 대상의 가장 왼쪽 값인 2와 바꿉니다.
1 | 4 5 2 3 ← 1을 대상에서 제외하고 4, 5, 2, 3에서 최솟값을 찾습니다.
1 | 2 5 4 3 ← 4, 5, 2, 3 중 최솟값인 2를 4와 바꿉니다.
1 2 | 5 4 3 ← 2를 대상에서 제외하고 5, 4, 3에서 최솟값을 찾습니다.
1 2 | 3 4 5 ← 5, 4, 3 중 최솟값인 3을 5와 바꿉니다.
1 2 3 | 4 5 ← 3을 대상에서 제외하고 4, 5에서 최솟값을 찾습니다.
1 2 3 | 4 5 ← 최솟값 4를 4와 바꿉니다(변화 없음).
1 2 3 4 | 5 ← 4를 대상에서 제외합니다. 자료가 5 하나만 남았으므로 종료합니다.
1 2 3 4 5 | ← 최종 결과
잠깐만요
정렬 중간 결과 출력하기
다음과 같이 함수 반복 부분에 print(a)를 추가하면 정렬 과정의 중간 결과를 화면에서 쉽게 확인할 수 있습니다.
def sel_sort(a):
n = len(a)
for i in range(0, n - 1):
min_idx = i
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
print(a) # 정렬 과정 출력하기
d = [2, 4, 5, 1, 3]
sel_sort(d)
print(d)