삽입정렬

import java.util.Scanner;

public class Main {
    public int[] solution(int n, int[] arr) {
        //i가 1일 때 j가 도는데 j는 -1에서 멈춘다
        //멈춘 -1의 +1 부분에 j값을 넣어준다.
        for(int i = 1; i < n; i++) {
            int tmp = arr[i], j;
            for(j = i-1; j >= 0; j--) {
                if(arr[j] > tmp) arr[j+1] = arr[j];
                else break;
            }
            arr[j+1] = tmp;
        }

        return arr;
    }

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

    }
}