삽입 정렬

[Java] 삽입 정렬 알고리즘 이해하기

Dec 18, 2023

Contents

삽입 정렬(insertion sort)

목표 : 오름 차순

⚡

원본 데이터 (5, 8, 2, 4, 3) N

알고리즘 작성 해보기

1회전(1바퀴) k = arr[1]

8, 5 비교 변함없음

2회전(2바퀴) k = arr[2]

2, 8 비교 작음

2, 5 비교 작음 (2, 5, 8, 4, 3)

3회전(3바퀴)

4, 8 비교 작음

4, 5 비교 작음

4, 2 비교 큼 (2, 4, 5, 8, 3)

4회전(4바퀴)

3, 8 비교 작음

3, 5 비교 작음

3, 4 비교 작음

3, 2 비교 큼 (2, 3, 4, 5, 8)

회전수 : N-1 n회전 비교 횟수 : N-n

알고리즘 그대로 코드 작성 해보기


package ex03.test;

import java.util.Arrays;

public class InsertSort01 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};
        int temp;

        // 1회전
        if(arr[1]<arr[0]){
            //스왑
            temp = arr[1];
            arr[1] = arr[0];
            arr[0] = temp;
        }
        System.out.println(Arrays.toString(arr));

        // 2회전
        if(arr[2]<arr[1]){
            if(arr[2]<arr[0]){
                // 스왑
                temp = arr[2];
                arr[2] = arr[1];
                arr[1] = arr[0];
                arr[0] = temp;
            }else{ // arr[2]>arr[0]
                temp = arr[2];
                arr[2] = arr[1];
                arr[1] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));

        // 3회전
        if(arr[3]<arr[2]){
            if(arr[3]<arr[1]){
                if(arr[3]<arr[0]){
                    temp = arr[3];
                    arr[3] = arr[2];
                    arr[2] = arr[1];
                    arr[1] = arr[0];
                    arr[0] = temp;
                }else{
                    temp = arr[3];
                    arr[3] = arr[2];
                    arr[2] = arr[1];
                    arr[1] = temp;
                }
            }else{
                temp = arr[3];
                arr[3] = arr[2];
                arr[2] = temp;

            }
        }
        System.out.println(Arrays.toString(arr));

        // 4회전
        if(arr[4]<arr[3]){
            if(arr[4]<arr[2]){
                if(arr[4]<arr[1]){
                    if(arr[4]<arr[0]){
                        temp = arr[4];
                        arr[4] = arr[3];
                        arr[3] = arr[2];
                        arr[2] = arr[1];
                        arr[1] = arr[0];
                        arr[0] = temp;
                    }else{
                        temp = arr[4];
                        arr[4] = arr[3];
                        arr[3] = arr[2];
                        arr[2] = arr[1];
                        arr[1] = temp;
                    }
                }else{
                    temp = arr[4];
                    arr[4] = arr[3];
                    arr[3] = arr[2];
                    arr[2] = temp;
                }
            }else{
                temp = arr[4];
                arr[4] = arr[3];
                arr[3] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));

    }
}

모듈화를 통해 간단한 코드 만들기


package ex03.test;

import java.util.Arrays;

public class InsertSort01 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};

        for(int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for(j = i - 1; j >= 0 && arr[j] > temp; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = temp;
            System.out.println(Arrays.toString(arr));
        } 
    }
}

package ex03.test; import java.util.Arrays; public class InsertSort01 { public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; int temp; // 1회전 if(arr[1]<arr[0]){ //스왑 temp = arr[1]; arr[1] = arr[0]; arr[0] = temp; } System.out.println(Arrays.toString(arr)); // 2회전 if(arr[2]<arr[1]){ if(arr[2]<arr[0]){ // 스왑 temp = arr[2]; arr[2] = arr[1]; arr[1] = arr[0]; arr[0] = temp; }else{ // arr[2]>arr[0] temp = arr[2]; arr[2] = arr[1]; arr[1] = temp; } } System.out.println(Arrays.toString(arr)); // 3회전 if(arr[3]<arr[2]){ if(arr[3]<arr[1]){ if(arr[3]<arr[0]){ temp = arr[3]; arr[3] = arr[2]; arr[2] = arr[1]; arr[1] = arr[0]; arr[0] = temp; }else{ temp = arr[3]; arr[3] = arr[2]; arr[2] = arr[1]; arr[1] = temp; } }else{ temp = arr[3]; arr[3] = arr[2]; arr[2] = temp; } } System.out.println(Arrays.toString(arr)); // 4회전 if(arr[4]<arr[3]){ if(arr[4]<arr[2]){ if(arr[4]<arr[1]){ if(arr[4]<arr[0]){ temp = arr[4]; arr[4] = arr[3]; arr[3] = arr[2]; arr[2] = arr[1]; arr[1] = arr[0]; arr[0] = temp; }else{ temp = arr[4]; arr[4] = arr[3]; arr[3] = arr[2]; arr[2] = arr[1]; arr[1] = temp; } }else{ temp = arr[4]; arr[4] = arr[3]; arr[3] = arr[2]; arr[2] = temp; } }else{ temp = arr[4]; arr[4] = arr[3]; arr[3] = temp; } } System.out.println(Arrays.toString(arr)); } }

package ex03.test; import java.util.Arrays; public class InsertSort01 { public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; for(int i = 1; i < arr.length; i++) { int temp = arr[i]; int j; for(j = i - 1; j >= 0 && arr[j] > temp; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = temp; System.out.println(Arrays.toString(arr)); } } }