Back/Java
[선택 정렬] 서치 정리
자바꿈나무00
2022. 11. 29. 16:45
- Selection Sort [선택 정렬] : 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘.
*또 다른 이름 (__ __)정렬?
- '비교 정렬' 데이터를 '비교'하면서 찾아서 비교정렬.
- '제자리 정렬(in-place sort)'정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않아 제자리 정렬.
(정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다.)
-'불안정 정렬'
*정렬 방법
1. 주어진 리스트에서 최솟값을 찾는다.
2. 최솟값을 맨 앞 자리의 값과 교환한다.
3. 맨 앞 자리를 제외한 나머지 값들 중 최솟값을 찾아1, 2를 반복한다.
* 마지막 round9 를 안하는 이유: 앞 인덱스부터 순차적으로 정렬해나가기 때문에
N개의 데이터 중 N-1개가 정렬 되어있다는 것은 마지막 원소가 최댓값이라는 말이고,
이는 정렬이 되어있다는 상태이므로 굳이 참조를 해줄 필요 없다.
* 선택 정렬 구현하기
https://st-lab.tistory.com/168
public class Selection_Sort {
public static void selection_sort(int[] a) {
selection_sort(a, a.length);
}
private static void selection_sort(int[] a, int size) {
for(int i = 0; i < size - 1; i++) {
int min_index = i;
// 최솟값을 갖고있는 인덱스 찾기
for(int j = i + 1; j < size; j++) {
if(a[j] < a[min_index]) {
min_index = j;
}
}
// i번째 값과 찾은 최솟값을 서로 교환
swap(a, min_index, i);
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}일반적으로 C++에서는 두 데이터를 교환할 수 있는 swap() 함수가 있으나, 자바에서는 없기 때문에 따로 구현해주는 것이 편리하다.
*장단점
- 장점: 추가적인 메모리 소비가 적다.
- 단점: 시간 복잡도가 O(N2)이다, 안정 정렬이 아니다.
