인프런 - 삽입정렬

import java.util.*;
class Main {	
	public int[] solution(int n, int[] arr){
        for(int i =1; i<n; i++){
            int tmp=arr[i], j;
            for(j=i-1; j>=0; j--){ // i-1값부터 0까지
                if(arr[j]>tmp) arr[j+1] = arr[j]; // j값이(i-1) i보다 작으면 arr 뒤로 밀기
                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+" ");
	}
}