Selection Sort
- 처음 index부터 마지막 index까지의 이동하며 최대값을 찾은 후 저장하는 방식
- k-index에 들어갈 원소를 찾기위해서 k-1번 최대값을 찾는 비교를 해야하므로 O(n^2)이다.
동작
Step1
Step2
Step3
Step4
Step5
Step6
코드 (Java)
public class Sort {
public void swap(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
public void selectionSort(int[] arr) {
for(int i = arr.length-1; i >= 0; i--) {
int maxIndex = i;
int j;
for(j = 0; j < i; j++) {
if(arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
swap(arr, i, maxIndex);
}
}
}
'Algorithm' 카테고리의 다른 글
[Algorithm] 정렬 - Insertion Sort (삽입 정렬) (0) | 2021.09.15 |
---|---|
[Algorithm] 정렬 - Bubble Sort (거품 정렬) (0) | 2021.09.13 |
[Algorithm] 그래프 (Graph) (0) | 2021.04.14 |
[Algorithm] 문장의 유사도 분석 - 편집 거리 알고리즘 (Levenshtein Distance) (0) | 2021.01.20 |
[Algorithm] Dynamic Programming - Longest Common Sequence(LCS) (0) | 2020.11.12 |