3. 삽입 정렬

import java.util.*;

class Main {
	public ArrayList<Integer> solution(int N, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<>();
		answer.add(Integer.MIN_VALUE);
		answer.add(arr[0]);
		answer.add(Integer.MAX_VALUE);
		for (int i = 1; i < N; i++) {
			for (int j = 1; j < answer.size(); j++) {
				if (arr[i] >= answer.get(j - 1) && arr[i] <= answer.get(j)) {
					answer.add(j, arr[i]);
					break;
				} else
					continue;
			}
		}
		answer.remove(0);
		answer.remove(answer.size() - 1);
		return answer;
	}

	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 + " ");
		kb.close();
	}
}

이건 줄 알았는데 짜고보니 삽입정렬이 이게 아니었다

 

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--) {
				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 + " ");
		kb.close();
	}
}