삽입정렬(Insertion sort)

삽입정렬(Insertion Sort)

정렬 알고리즘은 데이터를 특정한 기준에 따라 순서대로 나열한 것을 말한다. 프로그램에서 데이터를 가공할 떄 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해 사용하는 경우가 많아서 가장 많이 사용되는 알고리즘이다. 데이터를 정렬하면 이진탐색(Binary Search)이 가능하다.

 

삽입정렬은 특정한 데이터를 적절한 위치에 ‘삽입’한다는 의미에서 삽입정렬이다. 따라서 삽입정렬은 선택정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간측면에서 더 효율적이다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬되어있을 때’ 훨씬 효율적이다. 선택 정렬은 현재데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸면 반면 삽입 정렬을 그렇지 않다.

그리고 삽입정렬은 두번째 데이터부터 시작한다. 왜냐하면 첫번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.

 

 

 

Java Code

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {3, 4, 6, 8, 7, 5, 0, 2, 1};

        //삽입정렬은 2번째 부터 시작
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j;

            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j]; //뒤쪽으로 밀기
                } else {
                    //오름차순이라면 이미 앞에서 정렬이 되었기 때문에 j문을 빠져나감.
                    break;
                }
            }
            /*
             * j문을 다 돌았을 때 값 넣기
             * j문이 끝났다는 의미는 앞의 원소가 타켓(tmp)보다 작다는 의미이므로 타겟 원소는 j번째 원소 뒤에 와야하므로 j+1에 위치
             */
            arr[j + 1] = tmp;
        }
        System.out.print("Sorted Array :" + Arrays.toString(arr));

    }
}

 

삽입정렬의 시간복잡도

최악의 경우(역으로 정렬되어 있을 경우) 선택 정렬과 마찬가지로 ,

첫번째 회전에서 1번, 두번째 회전에서 2번 + … + (N-1)번 수행되므로

(N-1) + (N-2) + … + 2 + 1 = n(n-1)/2 이다. 즉, 시간복잡도는 O(N^2)이다.

하지만 원소가 이미 정렬되어 있는 경우 외부 루프를 N-1번을 도는 동안 비교 연산은 1번씩 수행되므로 최선의 경우 O(N) = N 이 된다.

삽입정렬의 공간복잡도

주어진 배열 안에서 교환을 하므로 O(N)이다.

삽입정렬의 특징

1. 제자리 정렬 알고리즘(in-place sorting)의 하나로 배열이외의 다른 추가 메모리를 요구하지 않는다.
2. 이미 정렬되어 있는 경우 매우 효율적이다.
3. 시간복잡도가 O(N^2)이므로 최악의 경우 일때, 만약에 정렬해야 할 개수가 100배 늘어나면 수행시간은 10,000배로 늘어나기때문에 비효율적이다.