[알고리즘] 삽입 정렬 with Java

 

3. 삽입 정렬

 

설명

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

정렬하는 방법은 삽입정렬입니다.

입력

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

출력

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

예시 입력 1 

6
11 7 5 6 10 9

예시 출력 1

5 6 7 9 10 11

 

오늘 배운 것

1. 삽입 정렬

. 간단하게 변경만 해주면 되는 작업이다. 뒤에서부터 하나씩 채워가며 제일 큰 것을 쌓아준다.

2. 문제 풀이

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int N = kb.nextInt();
        int [] arr = new int [N];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = kb.nextInt();
        }
        solution(arr);
    }

    private static void solution(int[] arr) {
        int i,j,key;
        for (i = 1; i < arr.length; i++) {
            key = arr[i];

            for(j = i-1 ; j >= 0 && arr[j] > key ; j--){
                arr[j+1] = arr[j];
            }
            arr[j+1] = key;
        }
        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k]+" ");
        }
    }
}