일반 로직
- 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
- 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.
public class SelectionSort {
public static void main(String[] args) {
int[] arr = new int[]{2, 7, 4, 9, 10, 223, 111, 23, 3, 39};
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
for (int j = i; j < arr.length; j++) {
if(arr[minIdx] > arr[j]) minIdx = j;
}
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
System.out.println(Arrays.toString(arr));
}
}
}int minIdx = i; 선택 정렬은 0인덱스 부터 마지막 인덱스까지 비교하여 제일 작은 인덱스 번호를 찾아 그 번호 안에 있는 숫자를 0번째와 바꿔준다. 그렇기 때문에 한 루프를 돌 때마다 i인덱스가 시작점이므로 i를 시작점으로 한다.
for (int i = 0; i < arr.length - 1; i++) 루프를 전부 돌릴 필요 없이 마지막 인덱스 값은 뒤에 번호를 비교할 곳이 없기 때문에 -1 을 해준다.
for (int j = i; j < arr.length; j++) {
if(arr[minIdx] > arr[j]) minIdx = j;
}j는 i 부터 시작해야한다. i번째 부터 그 뒤에 수까지 하나하나 비교해서 최소값을 찾는것이 선택 정렬이기 때문이다. 그리고 여기서 if문으로 arr[minIdx] 보다 arr[j ] 가 작다면 minIdx를 j번째로 넣어준다
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
System.out.println(Arrays.toString(arr));if문이 실행되고 조건에 맞으면 촤소인덱스도 바꿔주면서 값을 스왑해준다. temp에 arr[i] 수를 넣어주고
arr[i] 는 최소값이 들어있는 인덱스의 수와 바꿔 줘서 저장한다. 그 이후 arr[minIdx] 에는 arr[i]값이 들어있는 최소값에 arr[i] 를 넣어준다 arr[i]가 더 크기 때문이다.
확장성을 생각한 응용 로직
interface StatementStrategy {
boolean apply(int a, int b);
}
// interface를 선언하고
// Template Callback패턴
public class SelectionSort {
public int[] selectionSort(int[] arr, StatementStrategy stmt) {
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
for (int j = i; j < arr.length; j++) {
if (stmt.apply(arr[minIdx], arr[j])) minIdx = j;
}
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
System.out.println(Arrays.toString(arr));
}
return arr;
}
public static void main(String[] args) {
int[] arr = new int[]{2, 7, 4, 9, 10, 223, 111, 23, 3, 39};
SelectionSort ss = new SelectionSort();
ss.selectionSort(arr, (a, b) -> a < b);
ss.selectionSort(arr, (a, b) -> a > b);
}
}템플릿 콜백 패턴을 사용하여 오름차순 내림차순을 그때마다 정할 수 있게 만들 수 있다.
interface StatementStrategy {
boolean apply(int a, int b);
}
// interface를 선언하고
// Template Callback패턴
public class SelectionSort {
public int[] selectionSort(int[] arr, StatementStrategy stmt) {
확장성을 이용하기 위해 인터페이스로 만들고 메서드는 함수를 사용할 때 직접 구현할 수 있게 만들어 준다.
boolean인 이유는 if문만 두개의 차이가 있으므로 바꿔준다. 그리고 selecitonSort메서드 파라미터에 인터페이스를 넣어주고 메서드를 사용할때 마다 원하는 모양으로 바꿀수 있게 해준다.
if (stmt.apply(arr[minIdx], arr[j])) minIdx = j;
}if문안에 true false의 기준에 따라 오름차순 내림차순이 바뀌기 때문에 여기에 적용하여 메서드에 있는 a,b를 여arr[j] 와 arr[minIdx]로 넣어준다
public static void main(String[] args) {
int[] arr = new int[]{2, 7, 4, 9, 10, 223, 111, 23, 3, 39};
SelectionSort ss = new SelectionSort();
ss.selectionSort(arr, (a, b) -> a < b);
ss.selectionSort(arr, (a, b) -> a > b);클래스를 구현하고 메서드 파라미터 안에 인터페이스를 넣었으니까 배열을 넣고 인터페이스 안에 익명객체를 넣어주면 되는데 쉽고 간단하게 사용하기 위해 lambda를 사용한다. (a,b) 인터페이스 메서드 파라미터이고 → 리턴문 이나 결과값이 오면 된다.
lambda (람다, 표현식, 함수형 인터페이스, default 메소드, 메소드 레퍼런스)
Function<T, R> 를 이용하여 구현
public class BiFun {
public int[] selectionSort(int[] arr, BiFunction<Integer, Integer, Boolean> stmt) {
for (int i = 0; i < arr.length - 1; i++) {
int swapIdx = i;
for (int j = i; j < arr.length; j++) {
if (stmt.apply(arr[swapIdx], arr[j])) swapIdx = j;
}
int temp = arr[i];
arr[i] = arr[swapIdx];
arr[swapIdx] = temp;
System.out.println(Arrays.toString(arr));
}
return arr;
}
public static void main(String[] args) {
int[] arr = new int[]{34,5,436,6,7,3,10};
BiFun bf = new BiFun();
bf.selectionSort(arr, (a,b) -> a < b);
}
}템플릿 콜백 패턴은 자주 사용하는 패턴이기에 자바에서 미리 비슷한 기능을 인터페이스 형식으로 지원해주는데 그게 바로 BiFunction이다. 비교할 두 숫자를 랩퍼클래스에 받아주고 마지막 boolean을 넣어줌으로써 비교후 boolean으로 반환을 해준다. BiFunction<사용할 타입, 사용할 타입 , 리턴타입> 사용할 때에는 람다나 익명객체로 반드시 구현해야함
