개념
- i 번 자리에 어떤 값이 오면 될지 '선택'바꾸는 정렬
: 1번째부터 수부터 맨 끝 수까지 훑어서 가장 작은 걸 첫번째로 스왑한다. 그 다음에는 2번째부터 끝까지 훑어서 가장 작은 게 두번째.. 반복해서 정렬한다. (버블정렬과 비슷) - 시간복잡도는 O(N^2)
- 시각자료 : https://youtu.be/92BfuxHn2XE
- 참고: 버블정렬 - 바로 뒤의 원소와 비교해 더 크다면 뒤로 가면서 처음끝까지 훑으면서, 교환도 그때마다 일어나 효율이 매우 안좋다. O(N^2)
선택정렬과 비교시 처음부터 끝까지 다 훑는다는점이 같지만 선택정렬은 교환을 1순회시 한번만 한다는것이 버블정렬과 다르다. (하지만 시간복잡도는 결국같다)
구현
🔽 오류 code
public class Selection {
public static void main(String[] args) {
int[] arr = new int[]{2, 7, 4, 9, 10, 223, 111, 23, 3, 39};
int minIdx = 0;
// 제일 작은값 찾기
for (int i = 0; i < arr.length - 1; i++) { // 스왑기준(배열인덱스값 0~n-1)
for (int j = i + 1 ; j < arr.length; j++) { // 비교
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
System.out.println(j+"번째) " + "minValue: " + arr[minIdx] + " minIdx : " + minIdx );
}
// 스왑
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
System.out.println(i+"번째) " + Arrays.toString(arr));
}
}
}🔽 오류 결과
idx(1) - minValue: 2 minIdx : 0
idx(2) - minValue: 2 minIdx : 0
idx(3) - minValue: 2 minIdx : 0
idx(4) - minValue: 2 minIdx : 0
idx(5) - minValue: 2 minIdx : 0
idx(6) - minValue: 2 minIdx : 0
idx(7) - minValue: 2 minIdx : 0
idx(8) - minValue: 2 minIdx : 0
idx(9) - minValue: 2 minIdx : 0
0번째 결과) [2, 7, 4, 9, 10, 223, 111, 23, 3, 39]
idx(2) - minValue: 2 minIdx : 0
idx(3) - minValue: 2 minIdx : 0
idx(4) - minValue: 2 minIdx : 0
idx(5) - minValue: 2 minIdx : 0
idx(6) - minValue: 2 minIdx : 0
idx(7) - minValue: 2 minIdx : 0
idx(8) - minValue: 2 minIdx : 0
idx(9) - minValue: 2 minIdx : 0
1번째 결과) [7, 2, 4, 9, 10, 223, 111, 23, 3, 39] -> 여기서 7 이 튀어나오면 안된다.
idx(3) - minValue: 7 minIdx : 0
...(생략)
8번째 결과) [7, 2, 3, 4, 9, 10, 23, 39, 111, 223] -> 1번째 결과에서 튀어나온 7 말고는 정렬이 다 되었다. 코드 수정 흐름
swap문을 잘못 썼나 의심 -> 배열 출력문을 추가하여 배열 정렬 결과를 볼 수 있도록 바꿈. print 결과를 보니 8번째(마지막)결과가7말고는 정렬된것을 보고 다른 문제점을 찾아봄- idx변화를 찍는 print문을 추가 ->
i를 한번 돌리고 나서의minIdx가 내 예상대로i+1이 되지 않은것을 확인함 - 결론도출: for문 바깥에 선언한
int minIdx = 0;을 i for문 안에 넣어주어 값이 증가될 수 있도록 하였다.
- 아예 틀린 코드에 우연찮게도
7이라는 하나의 값 말고는 정렬이 잘 되어서 해결하기 더 어렵고 헷갈렸다. 그래서7이 튀어나온 단계에만 집착했는데 결과가 예상 밖으로 나왔을때 반복문 안의 변화를 다 찍어보며 전체를 다시 살펴보는 습관이 중요할것 같다.
🔽 고친 code
ublic class Selection {
public static void main(String[] args) {
int[] arr = new int[]{2, 7, 4, 9, 10, 223, 111, 23, 3, 39};
// int minIdx = 0;
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i; //
// ...밑의 코드 생략
}🔽 실행 결과
[2, 3, 4, 7, 9, 10, 23, 39, 111, 223]
🔽 Selection.java 리팩토링 code
리팩토링 방향: 오름차순/내림차순 둘다 가능하게 한다.
1. interface를 선언하고
2. Template Callback패턴 적용
interface StatementStrategy{
boolean compare(int a, int b);
}
public class SelectionRefactoring {
public int[] sort(int arr[], StatementStrategy stmt){
int minIdx = 0;
int tmp;
for (int i = 0; i < arr.length-1; i++) {
minIdx = i;
for (int j = i+1; j < arr.length; j++) {
if (stmt.compare(arr[minIdx] , arr[j])) {
minIdx = j;
}
}
tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
return arr;
}
public static void main(String[] args) {
int[] arr = {2, 7, 4, 9, 10, 223, 111, 23, 3, 39};
SelectionRefactoring ss = new SelectionRefactoring();
System.out.println(Arrays.toString(ss.sort(arr, (a, b) -> a > b))); //오름차순
System.out.println(Arrays.toString(ss.sort(arr, (a, b) -> a < b))); //내림차순
}
}Function<T,R> Interface
// Function<T,R> 인터페이스 - T는 입력타입, F는 리턴타입
Function<Integer[], Boolean > fn = (arr1) -> arr1[0] > arr1[1];
System.out.println(fn.apply(new Integer[]{10,20}));BiFunction<T,T,R> Interface
// 앞에 두개 타입을 Integer a, Integer b로 받아서 True or False로 리턴
BiFunction<Integer, Integer, Boolean> bifn = (a, b) -> a > b;