[JAVA] 정렬 알고리즘 삽입 정렬 (Insertion Sort)

지난 포스팅에서 버블 정렬(Bubble Sort)와 선택 정렬(Selection Sort)를 포스팅 해보았습니다.

오늘은 지난 포스팅과 더불어 시간복잡도 O(N²)을 갖는 기초적인 정렬 중 하나인 삽입 정렬(Insertion Sort)에 대해 알아보겠습니다.

 

삽입 정렬(Insertion Sort)

삽입 정렬(揷入整列, Insertion Sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

*위키백과 참조

https://velog.io/@yujo/JS%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%ACInsertion-Sort 참조

 

위키백과의 설명이 조금은 이해가 가지 않을 수 있기 때문에, 아래 그림을 통해 이해를 돕도록 하겠습니다.

 

정렬이 안된 초기상태의 배열이 있습니다.

삽입정렬에서는 가장 첫번째 원소는 정렬이 된 상태라고 가정을 하고 시작을 합니다. ( 이유는 원소가 1개면 10이 오든 100이 오든 이미 정렬이 끝난 상태기 때문에 )

그렇기 때문에 두번째 원소부터 비교해 나가기 시작합니다.

두번째 원소인 1을 왼쪽 원소들과 비교하여 올바른 위치인 5의 앞으로 위치하게 됩니다.

다음 세번째 원소인 3보다 왼쪽 원소들을 비교하여 올바른 위치인 1과 5 사이에 위치합니다. 

네번째 7은 이미 올바른 곳이므로 교환하지 않습니다.

다섯번째 2보다 앞의 원소들을 비교해 올바른 자리를 찾습니다.

이와 같은 과정들을 반복하여 정렬을 마칩니다.

 

 

이미지 참조

https://m.blog.naver.com/PostView.nhn?blogId=justant&logNo=20204025251&proxyReferer=https:%2F%2Fwww.google.com%2F

---

삽입 정렬(Insertion Sort) 구현 (For문)

public class insertionSort {
 
    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = i;
 
            for (int j = i - 1; j >= 0; j--) {
                if (array[key] < array[j]) {
                    swap(array, key, j);
                    key = j;
                }
            }
        }
    }
 
    public static void swap(int[] array, int source, int target) {
        int temp = array[source];
        array[source] = array[target];
        array[target] = temp;
    }
 
    public static void printArray(int[] array) {
        for (int data : array) {
            System.out.print(data + " ");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        int[] item = new int[] { 5, 1, 3, 7, 2, 9 };
        System.out.println("삽입정렬 전 :");
        printArray(item);
        System.out.println("삽입정렬 후 :");
        insertionSort(item);
        printArray(item);
    }
 
}

 

결과값

삽입 정렬(Insertion Sort)의 구현은 다음과 같습니다.

코드의 설명을 돕자면 다음과 같습니다.

insertionSort의 메소드는 배열을 인자값으로 받습니다.(3번째줄)

첫번째 For문(외부)에서 두번째 값부터 배열의 끝까지 정렬을 합니다. (4번째줄)

이때, key값은 두번째 원소로 설정합니다. (여기서는 i) (5번째줄)

두번째 For문(내부)에서 key값의 왼쪽 원소들을 정렬합니다. (7번째줄)

이때, 키값보다 큰 원소가 있으면 위치를 교환한 후 다음 원소를 key값으로 저장합니다. (8~10번째줄)

 

이해가 가지 않으신다면, [더보기]를 통해 명시적으로 확인해 보시길 바랍니다.

public class insertionSort {
    
    public static void insertionSort(int[] array) {
        for(int i = 1; i<array.length; i++) {
            int key = i;
            for(int data : array) {
                System.out.print(data + " ");
            }
            System.out.println();
            
            for(int j = i-1; j>=0; j--) {
                if(array[key] < array[j]) {
                    swap(array, key, j);
                    key = j;
                }
            }
        }
    }
    
    public static void swap(int[] array, int source, int target) {
        int temp = array[source];
        array[source] = array[target];
        array[target] = temp;
    }
    
    public static void printArray(int[] array) {
        for(int data: array) {
            System.out.print(data + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] item = new int[] {5,1,3,7,2,9};
        System.out.println("버블 정렬 과정 ");
        insertionSort(item);
        
    }
 
}

 

결과값

---

while문을 이용한 삽입 정렬(Insertion Sort)

같은 방식이라도 여러가지 방법의 구현이 있습니다.

public class insertionSort {
 
    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = i;
            while (key > 0 && array[key - 1] > array[key]) {
                swap(array, key - 1, key);
                key--;
            }
        }
    }
 
    public static void swap(int[] array, int source, int target) {
        int temp = array[source];
        array[source] = array[target];
        array[target] = temp;
    }
 
    public static void printArray(int[] array) {
        for (int data : array) {
            System.out.print(data + " ");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        int[] item = new int[] { 5, 1, 3, 7, 2, 9 };
        System.out.println("삽입정렬 완료");
        insertionSort(item);
        printArray(item);
 
    }
 
}

 

이 외에도 LinkedList를 이용한 방법이 있지만, 현재 포스팅에서는 다루지 않겠습니다.

추후 LinkedList에 관한 포스팅 이후에 추가하도록 하겠습니다.

---

삽입 정렬(Insertion Sort) 정리

같은 시간복잡도O(N²)를 가지는 선택 정렬(Selection Sort)나 버블 정렬(Bubble Sort)에 비해 빠르고, 안정(Stable) 정렬이며, 제자리 정렬(in-place) 알고리즘이다.
최선의 경우 이미 정렬된 상태인 시간복잡도 O(N)을 가지며, 평균 및 최악은 시간복잡도 O(N²)을 가진다.
대부분의 레코드가 이미 정렬된 상태의 경우 매우 효율적일 수 있다.
레코드 수가 많고 레코드의 크기가 클 경우는 적합하지 않다.

---

다른 정렬들과의 시간복잡도 비교

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html 참조

---

그럼 2만