section6.3

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

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

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

입력예제 1
6
11 7 5 6 10 9

출력예제 1
5 6 7 9 10 11

 

 

 

ANSWER

public class Question3 {
    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) {
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            for (int j = i-1; j >= 0; j--) {
                if (arr[j] > key) {
                    int tmp = arr[j];
                    arr[j] = key;
                    arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }
}

 

 

 

SOLUTION

public class Answer3 {
    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) {
        for (int i = 0; i < n; i++) {
            int tmp = arr[i];
            for (int j = i-1; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j+1] = arr[j];
                } else {
                    break;
                }
                arr[j+1] = tmp;
            }
        }
        return arr;
    }
}

• 삽입 정렬 알고리즘에 대해 찾아보고 풀었더니 당연히 코드는 맞았다
• 아쉬운 점은 중간에 위치를 찾았을 때 break 하지 않아서 사실상 삽입 정렬 알고리즘을 사용했다고 하기 애매한 ...

 

 

 

삽입정렬 알고리즘

- 삽입 정렬은 두 번째 자료부터 시작하여 그 왼쪽 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다

- 두 번째 자료는 첫 번째 자료를, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동한다        

 

 

 

---

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