문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

Insertion Sort Part1에서 배열의 올바르게 정렬된 위치에 하나의 인자를 삽입했다. 동일한 방법을 반복 사용해서 전체 배열을 정렬할 수 있나?

Example

n = 7
arr = [3, 4, 7, 5, 6, 3, 2]

왼쪽부터 오른쪽까지 동작하고, 다음과 같은 결과를 얻는다.

3 4 7 5 6 2 1
3 4 7 5 6 2 1
3 4 5 7 6 2 1
3 4 5 6 7 2 1
2 3 4 5 6 7 1
1 2 3 4 5 6 7

Function Descirption

insertionSort2 함수를 완성해라.
insertionSort2 함수는 아래와 같은 매개변수를 가지고 있다.

• int n: arr의 길이
• int arr[n]: 정수형 배열

Prints

각 반복에서 배열을 공백으로 구분하여 출력해라.

Constraints

• 1 <= n <= 1000
• -10000 <= arr[i] <= 10000
• 0 <= i < n

Solved

Part1과 비슷하게 풀면 되지만 이번에는 매 반복마다 바뀐 결과를 출력한다.

처음에는 배열의 길이가 1부터 시작해서 1을 예외처리하고 나머지는 else문에 처리하면 된다.

if(n == 1){
	printArr(arr); // 출력하는 부분은 따로 메서드로 분리
}else{
	// ...
}

for문과 while문을 사용해서 비교하는 값을 옮겨가며 인자 위치를 바꿔준다.

if(n == 1){
	printArr(arr); // 출력하는 부분은 따로 메서드로 분리
}else{
	for(int i = 1; i < n; i++){
		int temp = arr.get(i); // 위치를 바꿀 값
		int j = i - 1; // 바꿀 위치

		// 기존의 값을 오른쪽으로 위치 변경
		while(j >= 0 && arr.get(j) > temp){
			arr.set(j + 1, arr.get(j));
			j--;
		}

		arr.set(j + 1, temp); // 바뀔 위치에 값 할당
		printArr(arr);
	}
}

All Code

public static void insertionSort2(int n, List<Integer> arr) {
	if(n == 1){
		printArr(arr);
	}else{
		for(int i = 1; i < n; i++){
			int temp = arr.get(i);
			int j = i - 1;

			while(j >= 0 && arr.get(j) > temp){
				arr.set(j + 1, arr.get(j));
				j--;
			}

			arr.set(j + 1, temp);
			printArr(arr);
		}
	}
}

public static void printArr(List<Integer> arr){
	for(int i: arr){
		System.out.print(i + " ");
	}
        
	System.out.println();
}