선택정렬

1. 분석

선택정렬은 현재 위치에 들어갈 값을 찾아서 바꾸는 알고리즘이다. 오름차순으로 정렬하는 선택정렬은 다음과 같은 과정을 거친다.

2. 기능

1. 현재 정렬되지 않은 가장 맨 앞의 인덱스를 선택한다.
2. 현재 인덱스의 다음 인덱스부터 끝까지 가장 작은 값을 찾으면 현재 인덱스의 값과 바꿔준다.
3. 다음 인덱스에서 위 과정을 반복한다.

3. 구현

(1) 일반코드

public class SelectionSort {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public int[] solution(int[] arr){
        int[] result = arr;

        for(int i=0; i<arr.length; i++){
            int minidx = i;
            for(int j=i; j<arr.length; j++){
                if(result[minidx]>result[j])
                    minidx = j;
            }
            int temp = result[i];
            result[i] = result[minidx];
            result[minidx] = temp;
        }

        return result;
    }


    public static void main(String[] args) throws IOException {
        SelectionSort s = new SelectionSort();
        String[] temp = br.readLine().split(" ");
        int[] arr = new int[temp.length];

        for(int i=0; i<temp.length; i++){
            arr[i] = Integer.parseInt(temp[i]);
        }

        System.out.println(Arrays.toString(s.solution(arr)));
    }
}

• 사용자에게 문자열로 데이터를 입력받는다 이때, 공백을 기준으로 숫자를 구분하여 배열에 저장함
• String 배열을 int 배열로 이동시켜 저장함
• 배열에서 index n번부터 차례대로 n+1 이상의 값들과 비교해서 제일 작은수와 자리를 바꿔나감
• 최종적으로 오름차순된 배열 반환
  
  

(2) Interface Strategy(구조를 만들고 원하는 형식으로 사용)

interface StatementStrategy{
    boolean compare(int a, int b);
}

public class SelectionSort2 {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public int[] solution(int[] arr,StatementStrategy stmt){
            int[] result = arr;

            for(int i=0; i<arr.length; i++){
                int minidx = i;
                for(int j=i; j<arr.length; j++){
                    if(stmt.compare(result[minidx],result[j]))        // interface를 통해 값만 구현후 원하는 식에 넣어 사용
                        minidx = j;
                }
                int temp = result[i];
                result[i] = result[minidx];
                result[minidx] = temp;
            }

            return result;
        }


    public static void main(String[] args) throws IOException {
        SelectionSort2 s = new SelectionSort2();
        String[] temp = br.readLine().split(" ");
        int[] arr = new int[temp.length];

        for(int i=0; i<temp.length; i++){
            arr[i] = Integer.parseInt(temp[i]);
        }
        System.out.println(Arrays.toString(s.solution(arr,(a,b) -> a>b)));
        System.out.println(Arrays.toString(s.solution(arr,(a,b) -> a<b)));

//        int[] r = s.solution(arr, new StatementStrategy() {
//            @Override
//            public boolean compare(int a, int b) {
//                return a>b;
//            }
//        });

    }
}

• 일반 코드를 오름차순, 내림차순 2개를 구현하기 위해 인터페이스를 사용함
• 인터페이스를 내부 클래스를 사용하여 비교하는 방식만 바꿔서 사용할 수있도록 함
• 인터페이스를 사용한 이유는 코드의 재사용을 줄이기 위해 사용

(3) Function 사용

public class SelectionSort3 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    // BiFunction을 사용한 풀이
    public int[] solution(int[] arr, BiFunction<Integer,Integer,Boolean> stmt){
        int[] result = arr;

        for(int i=0; i<arr.length; i++){
            int minidx = i;
            for(int j=i; j<arr.length; j++){
                if(stmt.apply(arr[minidx],arr[j]))        // apply 결과값이 참일때 동작함
                    minidx = j;
            }
            int temp = result[i];
            result[i] = result[minidx];
            result[minidx] = temp;
        }

        return result;
    }

    // BiPredicate을 사용한 풀이 BiPredicate도 <Integer,Integer,Boolean>을 사용해야하지만 default값이 boolean이기 때문에 Boolean은 생략 가능
    public int[] solution2(int[] arr, BiPredicate<Integer,Integer> stmt){
        int[] result = arr;

        for(int i=0; i<arr.length; i++){
            int minidx = i;
            for(int j=i; j<arr.length; j++){
                if(stmt.test(arr[minidx],arr[j]))        // apply 결과값이 참일때 동작함
                    minidx = j;
            }
            int temp = result[i];
            result[i] = result[minidx];
            result[minidx] = temp;
        }

        return result;
    }


    public static void main(String[] args) throws IOException {

        SelectionSort3 s = new SelectionSort3();
        System.out.print("정렬할 값들을 입력하세요 :");
        String[] temp = br.readLine().split(" ");
        int[] arr = new int[temp.length];

        for(int i=0; i<temp.length; i++){
            arr[i] = Integer.parseInt(temp[i]);
        }

        BiFunction<Integer,Integer,Boolean> biFunction = (a,b) -> a>b;
        BiPredicate<Integer,Integer> biPredicate = (a,b) -> a<b;

     //   BiFunction<Integer,Integer,Boolean> biFunction2 = (a,b) -> a<b;

        System.out.println(Arrays.toString(s.solution(arr,biFunction)));
        System.out.println(Arrays.toString(s.solution2(arr,biPredicate)));
    }
}

• Function에 대한 자세한 설명은 람다&Function 정리 블로그 참고
• interface를 사용한 내부클래스 방식은 워낙 많이 사용하는 방식이라 function(함수)를 만들어 놓아서 가져다 사용하면 됨
• BiFunction, BiPredicate 2개를 사용하여 오름차순, 내림차순을 구현함

참고 자료 : 위키백과(선택정렬)