Selection Sort
- 처음 index부터 마지막 index까지의 이동하며 최대값을 찾은 후 저장하는 방식
- k-index에 들어갈 원소를 찾기위해서 k-1번 최대값을 찾는 비교를 해야하므로 O(n^2)이다.
https://en.wikipedia.org/wiki/Selection_sort
동작
Step1
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
Step2
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
Step3
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
Step4
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
Step5
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
Step6
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
코드 (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 |