Java 선택 정렬(Selection Sort)

선택정렬(Selection Sort)은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘이다.

오름차순 정렬은

첫 번째 순서에는 첫 번째 위치에 가장 최소값을 넣는다.
두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최소값을 넣는다.

세 번째 순서에는 세 번째 위치에 남은 값 중에서의 최소값을 넣는다.

......

 

1. 주어진 배열 중에서 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교환한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교환한다.
하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.

public class SelectionSort {
    public static void printArray(int[] a){
        for(int i = 0; i < a.length; i++){
            System.out.print("[" + a[i] + "]");
        }
        System.out.print("\n");
    }
 
    public static void main(String[] args) {
        int[] a = {95, 24, 68, 16, 53, 81};
 
        // 정렬 전의 배열 내용을 표시
        System.out.print("정렬 전 배열\n");
        printArray(a);
        System.out.print("\n");
 
        int[] aa = arr(a);
        // 정렬 후의 배열 내용 표시
        System.out.print("정렬 후 배열(오름차순)\n");
        printArray(aa);
 
        System.out.println("************************");
        int[] b = {95, 24, 68, 16, 53, 81};
        int[] bb = brr(b);
        // 정렬 후의 배열 내용 표시
        System.out.print("정렬 후 배열(내림차순)\n");
        printArray(bb);
 
    }
 
    private static int[] arr(int[] a) {
        // 선택 정렬(오름차순)
        int i, var, min, temp;
        for (i = 0; i < a.length -1 ; i++) {
            min = i;
            for (var = i + 1; var < a.length; var++) {
                // 맨 앞의 수를 하나씩 증가시키면서 값 비교하여 조건 비교 및 값 맞바꿈
                System.out.printf("i=%d, var=%d :: ",i, var);
                if (a[var] < a[i]) {
                    // 기준 값(i index)과 변동값(var index)을 비교하여
                    // 기준값(a[i])이 더 크면 맞바꿈 ==> 기준값 자리에 최소값을 넣음
                    min = var;
                    temp = a[i];
                    a[i] = a[min];
                    a[min] = temp;
                    System.out.printf(
                            "min=%d, temp=%d, a[%d]=%d, a[%d]=%d",
                            min,temp, i, a[i], min, a[min]
                    );
                }
                System.out.print("\n");
                printArray(a);
            }
        }
        return a;
    }
 
    private static int[] brr(int[] a) {
        // 선택 정렬(내림차순)
        int i, var, max, temp;
        for (i = 0; i < a.length -1 ; i++) {
            max = i;
            for (var = i + 1; var < a.length; var++) {
                // 맨 앞의 수를 하나씩 증가시키면서 값 비교하여 조건 비교 및 값 맞바꿈
                System.out.printf("i=%d, var=%d :: ",i, var);
                if (a[var] > a[i]) { // 배열 앞의 값이 더 크면
                    max = var;
                    temp = a[i];
                    a[i] = a[max];
                    a[max] = temp;
                    System.out.printf(
                            "max=%d, temp=%d, a[%d]=%d, a[%d]=%d",
                            max,temp, i, a[i], max, a[max]
                    );
                }
                System.out.print("\n");
                printArray(a);
            }
        }
        return a;
    }
 
}