선택 정렬(selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
예제
| 패스 | 테이블 | 최솟값 |
|---|---|---|
| 0 | [9,1,6,8,4,3,2,0] | 0 |
| 1 | [0,1,6,8,4,3,2,9] | 1 |
| 2 | [0,1,6,8,4,3,2,9] | 2 |
| 3 | [0,1,2,8,4,3,6,9] | 3 |
| 4 | [0,1,2,3,4,8,6,9] | 4 |
| 5 | [0,1,2,3,4,8,6,9] | 6 |
| 6 | [0,1,2,3,4,6,8,9] | 8 |
소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | void selectSort(int list[], int n) { for (int i = 0; i < n – 1; i++) { int low = i; for (int j = i + 1; j < n; j++) { if (list[low] > list[j]) { low = j; } } int tmp = list[i]; list[i] = list[low]; list[low] = tmp; } } | cs |
특징
알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
참조 : 위키백과