[정렬 알고리즘][파이썬] 선택 정렬

선택 정렬(selection sort)에서는 '수열 중에서 최소값을 검색해서 왼쪽 끝에 있는 숫자와 교체하는 작업을 반복합니다. 수열 중에서 최소값을 찾을 때는 선형 탐색을 사용합니다. -책 알고리즘 도감

 

 

위와 같이 서있는 막대기들을 선택 정렬을 사용해 오름차순으로 정렬해보겠습니다.

 

 

 

1. 선형 탐색을해서 최소값을 찾습니다.(여기서는 10) 그리고 왼쪽 끝에 있는 20과 자리를 바꿉니다. (만약, 최소값이 이미 왼쪽끝에 있다면 그대로 둡니다.) 그리고 이제 제일 왼쪽에 있는 10은 신경쓰지 않습니다.

 

 

 

2. 이제 남은 4개의 숫자중에서 최소값을 찾아서 20과 자리를 바꿉니다. 여기서는 4개의 숫자중 최소값이 20이므로 그대로 둡니다. 그리고 이제 정렬된 20도 신경쓰지 않습니다.

 

 

3. 이제 남은 3개의 숫자중에서 최소값을 찾아서 30과 자리를 바꿉니다. 여기서도 최소값이 제일 왼쪽에 있는 30이 최소값이므로 그래도 둡니다. 그리고 이제 30도 신경쓰지 않습니다.

 

4. 이제 남은 2개의 숫자중에서 최소값을 찾아서 50과 자리를 바꿉니다. 40이 더 작으므로 최소값이 되고 50과 자리를 바꿔줍니다.

 

참고 - 책 알고리즘 도감

 

---

[선택 정렬 코드] [파이썬]

if (min_index != i) 는 꼭 필요한 부분은 아닙니다.

 

 

[출력 결과]

 

[출력 해설]

1. i가 0일 때 / 안쪽 반복문을 돌고나면 min_index =  0->1 (min_index가 0에서 1로 바뀐다는 의미)(10이 최소값이니까!) 자리를 바꿔주고 [10, 20, 30, 50, 40]이 출력됩니다.

2. i가 1일 때 / 안쪽 반복문을 돌아도 min_index가 그대로입니다.(20이 최소값이므로!) 따라서, [10, 20, 30, 50, 40] 출력

3. i가 2일 때 / 안쪽 반복문을 돌아도 min_index가 그대로입니다.(30이 최소값이므로!) 따라서, [10, 20, 30, 50, 40] 출력

4. i가 3일 때 / 안쪽 반복문을 돌고나면 min_index = 3->4 따라서 자리를 바꿔주고 [10, 20, 30, 40, 50] 출력 -> 정렬 완료!

 

 

 

[보충 설명]

바깥 for문의 범위를 (0, len(arr))로 하지 않고 (0, len(arr)-1)로 한 이유는 선택 정렬의 특성상 i가 인덱스의 끝까지 가지 않아도 정렬이 완료되기 때문입니다. (이해안되시면 댓글 남겨주세요.)