section6.1

[선택정렬]
N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 선택정렬입니다.

입력설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

출력설명
오름차순으로 정렬된 수열을 출력합니다.

입력예제 1
6
13 5 11 7 23 15

출력예제 1
5 7 11 13 15 23

 

 

 

ANSWER

public class Question1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int x : solution(n, arr)) {
            System.out.print(x + " ");
        }
    }

    public static int[] solution(int n, int[] arr) {
        // 선택 정렬 > 배열 첫번재부터 비교하는데 min_value 찾아서 자리 바꿈
        for (int i = 0; i < n; i++) {
            int minValue = arr[i];
            int key = 0;
            Map<Integer, Integer> minMap = new HashMap<>();

            for (int j = i + 1; j < n; j++) {
                if (minValue > arr[j]) {
                    minValue = arr[j];
                    key = j;
                    if (minMap.isEmpty()) {
                        minMap.put(j, arr[j]);
                    } else {
                        minMap.clear();
                        minMap.put(j, arr[j]);
                    }
                } else {
                    // minValue <= arr[j]
                    if (minMap.isEmpty()) {
                        minMap.put(i, minValue);
                    } else {
                        minMap.clear();
                        minMap.put(i, minValue);
                        // 비어있지 않을 때 처리 필요
                    }
                }
            }
            if (arr[i] != minValue) {
                int tmp = arr[i];
                arr[i] = minValue;
                arr[key] = tmp;
            }
        }
        return arr;
    }
}

 

 

 

SOLUTION

public class Answer1 {
    public static void main(String[] args) {
        Answer1 T = new Answer1();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        for (int x : T.solution(n, arr)) {
            System.out.print(x + "  ");
        }
    }

    public int[] solution(int n, int[] arr) {
        for (int i = 0; i < n-1; i ++) {
            int idx = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[idx]) {
                    idx = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }
        return arr;
    }
}

 

 

 

선택정렬

- 제자리 정렬 알고리즘의 하나 > 정렬되지 않은 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

- 해당 순서에 원소를 넣을 위치는 이미 정해져 있고 어떤 원소를 넣을지 선택하는 알고리즘

- 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 비교하여 가장 작은 값을 찾아 첫 번째에 놓고 두 번째 자료를 세 번째 자료부터 마지막 자료까지 차례대로 비교하여 그중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다

- 1회전을 하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다    

 

---

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html