삽입정렬

삽입정렬

i는 1부터 시작해서 -> 방향으로 나아가고

j는 i-1부터 <- 방향으로 나가면서 정렬하는 방식

 

j값을 i-1 부터 해서 앞으로 작아지고

j가 멈춘 지점 바로 뒤에 tmp에 넣어둔 arr[i] 값을 넣는다

j는 안쪽 for문 밖에 넣어두고

마지막에 arr[j+1]에 tmp 값을 넣어준다

 

i 는 1 부터 시작하는 것과 내부 for문이 끝나고 나서 arr[j+1] 지점에 tmp 값 넣어주는 것을 꼭 기억하자!

import java.util.*;
import java.io.*;


class Main {
    public int[] solution(int n, int[] arr){
        //i는 1부터 시작
        for(int i = 1; i < n; i++){
            //j를 안쪽 for문 밖에 선언해둬야 안쪽 for문이 끝나도 쓸 수 있음
            int j = 0;
            int tmp = arr[i];
            //j가 0보다 작거나 같을때 까지 민다!
            for(j = i-1; j >= 0; j--){
                if(arr[j] > tmp) arr[j+1] = arr[j];
                else break;
            }
            //j가 감소한 상태로 오니 j+1 칸에 넣어주기
            arr[j+1] = tmp;
        }
        return arr;
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i =0; i < n; i++)arr[i] = in.nextInt();

        for(int x : T.solution(n, arr)) System.out.print(x + " ");
    }
}