가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘
void selectionSort(int[] arr) {
for(int i=0; i<arr.length-1; i++) { // 1.
int minIdx = i;
for(int j=i+1; j<arr.length; j++) { // 2.
if(arr[j] < arr[minIdx]) { // 3.
minIdx = j;
}
}
int temp = arr[minIdx]; // 4.
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
/* 배열의 크기를 n으로 가정 */
for(int i=0; i<n-1; i++) {
int minIdx = i;
for(int j=i+1; j<n; j++) {
if(arr[j] < arr[minIdx]) {
minIdx = j;
}
}
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
바깥 루프 i | 안쪽 루프 j에서의 비교 횟수 |
---|---|
i=0 | n-1 |
i=1 | n-2 |
i=2 | n-3 |
... | ... |
i=(n-2) | 1 |
📖 참고
- Bohyoh Shibata. (2020). Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바편(강민 옮김). 이지스퍼블리싱
- 선택 정렬 (Selection Sort)