삽입정렬(Insertion Sort)

개요

1번부터 시작해서(0번 아님)

현재까지의 위치에서 들어가야 할 곳에 Insert하는 정렬

 

 

과정

과정1

한단계씩 해보기

public static void main(String[] args) {
    int[] arr = new int[]{31, 25, 12, 22, 11};

    int start = arr[1]; // 25
    int back1 = arr[0]; // 31
    if (start < back1) { // 시작이 더 작으니 바꾼다
        int temp = back1;
        back1 = start;
        start = temp;
    }
    // 25, 31, 12, 22, 11
    start = arr[2]; // 12
    back1 = arr[1]; // 31
    if (start < back1) { // 시작이 더 작으니 바꾼다
        int temp = back1;
        back1 = start;
        start = temp;
    }
    // 25, 12, 31, 22, 11
}

 

과정2

일반 식 찾기

public static void main(String[] args) {
    int[] arr = new int[]{31, 25, 12, 22, 11};

    for (int i = 1; i < arr.length; i++) {
        System.out.println(arr[i]);
        // i가 1일 때 1과 0을 비교 i - 0, i - 1
        // i가 2일 때 2와 1을 비교 i - 0, i - 1
        ///          1과 0을 비교 i - 1, i - 2
        // i가 3일 때 3과 2를 비교 i - 0, i - 1
        ///          2와 1을 비교 i - 1, i - 2
        ///          1과 0을 비교 i - 2, i - 3
        int j = i; // 이 부분을 떠올려야 한다.
        // j가 0까지 빼줍니다.

    }

}

 

과정3

public static void main(String[] args) {
    int[] arr = new int[]{31, 25, 12, 22, 11};
    for (int i = 1; i < arr.length; i++) {
        // j가 0까지 빼줍니다.
        for (int j = i; j > 0; j--) {
            System.out.printf("i:%d j:%d j-1:%d \n", i, j, j-1);
            int now = arr[j]; // 25
            int back = arr[j-1]; // 31

            if (back > now) {
                int temp = arr[j-1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

 

 

완료

사용하지 않는 변수들을 제거

public static void main(String[] args) {
    int[] arr = new int[]{31, 25, 12, 22, 11};
    for (int i = 1; i < arr.length; i++) {
        // j가 0까지 빼줍니다.
        for (int j = i; j > 0; j--) {
            System.out.printf("i:%d j:%d j-1:%d \n", i, j, j-1);
            if (arr[j-1] > arr[j]) {
                int temp = arr[j-1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

 

 

Youtube

삽입정렬1 - 알고리즘 떠올리기

https://youtu.be/pWm4wRCy9pE

 

삽입정렬2 - 로직 구현하기

https://youtu.be/pWm4wRCy9pE