3. 삽입 정렬

1. 문제

삽입 정렬

 

 

2. 나의 풀이

로직만 보고 풀려했는데 자꾸 꼬여서 그냥 강의를 봤다.

 

실제로 그림 그려가면서 i 와 j 의 위치만 생각하면 된다.

 

C언어로 배우는 자료구조

 

3. 강의 코드

package Sort;

import java.util.*;
public class Sort_03_insertion {
    public static int[] solution(int[] arr, int n) {

        for (int i = 1; i < n; i++) {
            int target = arr[i];
            int j;
            //나보다 큰 아래 인덱스 값(j = i -1)들을 뒤로 미루고 나보다 작은 값이 나오면(j+1) 그 뒤에 저장한다.
            for (j = i - 1; j >= 0; j--) {
            if (arr[j] > target) arr[j + 1] = arr[j];
                else break;
            }
            arr[j + 1] = target;
        }

        return arr;
    }

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

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

 

4. 얻어갈 점

이건 내가 나중에 한 번 더 직접 짜보자!!