삽입정렬

문제

나의풀이

import java.util.*;
class Main {
	public int[] solution(int n,int[] arr) {
		for(int i=1; i<n;i++) {
			int tmp = arr[i];
			int j = 0;
			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 s = kb.nextInt();
		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 + " ");
	}
	
}

풀이방법

i번 바로 앞부터 탐색을 시작해서,
바로 전 값(j)이 tmp(i)보다 크다면 j가 j+1자리에 가고
tmp는 그 다음(j--)값과 비교하게된다.

tmp가 자신보다 작은값을 만나면 그 즉시 break;되고
j+1번째가 tmp의 위치이므로 삽입한다.

이때, j가 for문안에서 시작할때 생성됐다면 for문이 끝나면 사용하지 못하므로 j-for문 밖에서 설정해줘야한다!

핵심키워드

tmp는 arr[i]의 값을 갖는다.
j는 i바로 전부터 1씩 감소하면서 돈다.
j를 j-for문 밖에서 생성해주기.