[코드트리 조별과제] 삽입 정렬 구현

https://www.codetree.ai/missions/6/problems/implement-insertion-sort?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

 

풀이과정

1. target을 잡고 target의 앞에 위치한 값과 비교했을 때 앞의 값이 더 크다면 자리를 바꿔준다.
2. while문이 실행되면서 j는 0까지 감소하며, 정렬된 부분에서 target 요소보다 큰 값들이 오른쪽으로 이동됨. 이때 arr[j+1]에 arr[j]의 값을 대입하여 요소를 오른쪽으로 밀어내는 것.

 

나의 풀이

import java.util.*;

public class Main {

    private static int size;
    private static int[] arr;

    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);
        size = sc.nextInt();
        arr = new int[size];

        for(int i = 0; i < size; i++){
            arr[i] = sc.nextInt();
        }

        insertion_sort();

        for(int k = 0; k < arr.length; k++){
            System.out.print(arr[k] + " ");
        }
    }

    public static void insertion_sort(){
        for(int i = 1; i < size; i++){
            int target = arr[i];
            int j = i -1;

            while(j >= 0 && arr[j] > target){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = target;
        }
    }
}