삽입 정렬( Insertion sort ) 알고리즘

삽입 정렬 알고리즘?

배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘.
삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

특징

장점

• 레코드 수가 적거나 대부분의 레코드가 이미 정렬되어 있다면 매우 효율적이다.

단점

• 레코드 이동이 많을 수 있다.
• 레코드 수가 많고 크다면 적합하지 않다.

 

구현

public static void insertionSort( int[] target ) {
    for( int i = 1; i < target.length; i++ ){
        int pick = target[i];

        int j;
        for( j = i-1; j >= 0 && target[j] > pick; j-- ){
            // 오른쪽이동
            target[j+1] = target[j];
        }

        target[j+1] = pick;
    }
}

 

시간 복잡도

최상 : O(n)

평균, 최악 : O(n^2)

 

---

참고

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

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog