선택 정렬 (Selection Sort) 은 정렬 알고리즘 중 한가지로, 구현이 굉장히 간단합니다.
선택정렬을 한문장으로 요약하면 "가장 작은 것을 계속 앞으로 보낸다" 입니다.
최솟값을 계속 왼쪽에 보내면서, 왼쪽은 정렬된 리스트, 오른쪽은 정렬되지 않은 리스트로 만듭니다.
빨간색은 정렬되지 않은 리스트의 최솟값, 파란색은 빨간색 요소와 교환될 요소 (혹은 교환 후 위치), 초록색은 이미 정렬된 리스트를 뜻합니다.
리스트 안에서 교환만을 이용해 추가 공간 필요 없이(교환 할 때 생기는 tmp는 제외) 정렬한다는 점에서 제자리 정렬로 볼 수 있습니다.
| 1번 칸 | 2번 칸 | 3번 칸 | 4번 칸 | 5번 칸 |
|---|---|---|---|---|
| 5 | 4 | 1 | 3 | 2 |
| 5 | 4 | 1 | 3 | 2 |
| 1 | 4 | 5 | 3 | 2 |
| 1 | 4 | 5 | 3 | 2 |
| 1 | 2 | 5 | 3 | 4 |
| 1 | 2 | 5 | 3 | 4 |
| 1 | 2 | 3 | 5 | 4 |
| 1 | 2 | 3 | 5 | 4 |
| 1 | 2 | 3 | 4 | 5 |
| 1 | 2 | 3 | 4 | 5 |
i번째 원소로 i번째로 작은 값을 넣는다. 0번째부터 i - 1번째 원소로 이미 0번째로 작은 값부터 i - 1번째로 작은 값이 들어가있다. (== 정렬되어있다.) i번째부터 마지막 원소(n - 1번째 원소)까지 중에 가장 작은 값이 i번째로 작은 값이다. i번째부터 마지막 원소(n - 1번째 원소)까지 중에 가장 작은 값이 min_idx 번째 원소라고 하면, i번째 원소와 min_idx번째 원소를 서로 바꾼다. if arr[j] < arr[min_idx] 구문이 n - i - 1번 반복되고, i는 0부터 n - 2까지 반복됩니다. [3, 3, 4, 1]를 편의상 [3a, 3b, 4, 1]로 보면 정렬 후에 [1, 3b, 3a, 4]가 되어 같은 값인 3의 위치가 바뀌므로, 같은 값의 원래 순서가 보장되지 않음을 알 수 있습니다. 따라서 선택 정렬은 불안정 정렬입니다.