삽입 정렬

풀이>
삽입정렬: i가 1부터 iteration 하며 j는 i-1부터 0까지 1씩 줄여가면서 iteration
tmp에 arr[i]를 미리 넣어두고 tmp와 j를 비교하여 정렬하는 방식
->즉 i를 적절한 위치에 삽입하여 정렬

import java.util.*;
public 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--) {
                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 + " ");
        }
    }
}