[인프런_삽입 정렬] 3. 삽입 정렬

<<풀이>>

 

-강사님 풀이-

 

강사님께서 삽입 정렬로 문제를 푸셨다. 삽입 정렬이란 i = 1 부터 해서 왼쪽과 비교하여, 조건 충족시 자리 변환을 한다. 그렇게 해서 오름차순 혹은 내림차순을 하는 형태이다.

 

이 문제는 오름차순을 구하는 것이기에 왼쪽 부터 정렬이 되어간다.

값을 바꾸기 위해 임시보관 장소로 tmp를 활용했고, 

j값을 for문 블록에서 scope를 넓히기 위해 밖으로 빼줬다.

또한, for문을 다 돌면 끝났다고 생각하는데 잘 생각해보면 마지막 까지 for문 () 내의 변수는 변한다.

예를 들어,

j>=0 j--  이면 마지막에는 j가 -1 이 된다.

 

그렇기 때문에 실제로 데이터를 j를 활용해서 구하기 위해서는 이를 고려해서 넣어줘야 한다는 점이다 !!

 

import java.util.*;

class Main {
    private 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 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 + " ");
        }
    }
}

 

총 선택정렬, 버블정렬, 삽입 정렬 3개를 배웠는데, 잘 기억하자!!