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

Goal

• 삽입 정렬에 대해 설명할 수 있다.
• 삽입 정렬 과정에 대해 설명할 수 있다.
• 삽입 정렬을 구현할 수 있다.
• 삽입 정렬의 시간복잡도와 공간복잡도를 계산할 수 있다.

Abstract

삽입 정렬은 선택 정렬과 유사하지만, 좀 더 효율적인 정렬 알고리즘 방식이다.

삽입 정렬은 2번째 원소부터 시작하여, 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 갖고 있다.

Process

1. 정렬은 2번째 위치의 값을 temp에 저장한다.
2. temp와 이전에 있는 원소들과 비교하며 삽입한다.
3. 1번으로 돌아가 다음 위치의 값을 temp에 저장하고, 반복수행한다.

Code

void insertionSort(int[] arr) {
    for(int i = 1; i < arr.length; i++) {          // 1
    	int temp = arr[i];
        int prev = i - 1;
        while((prev >= 0) && (arr[prev] > temp)) { // 2
        	arr[prev+1] = arr[prev];
            prev--;
        }
        arr[prev+1] = temp;                        // 3
    }
    System.out.println(Arrays.toString(arr));
}

1. 첫 번째 원소 앞에는 어떤 원소도 갖고 있지 않기 때문에, 두 번째 위치부터 탐색을 시작한다. temp에 임시로 해당 위치 값을 저장하고, prev에는 해당 위치의 이전 위치를 저장한다.
2. 이전 위치를 가르키는 prev가 음수가 되지 않고, 이전 위치의 값이 1번에서 선택한 값보다 크다면, 서로 값을 교환해주고 prev를 더 이전 위치를 가르키도록 한다.
3. 2번에서 반복문이 끝난 후 prev에는 현재 temp값보다 작은 값들 중 제일 큰 값의 위치를 가리키게 된다. 따라서 (prev+1)에 temp값을 삽입한다.

시간복잡도

최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로 O(n^2)이다.

하지만, 모두 정렬이 되어있는 경우 한번씩 밖에 비교를 안하므로 O(n)시간 복잡도를 갖게 된다. 이미 정렬되어있는 배열에 자료를 하나씩 삽입/제거하는 경우에는 최고의 정렬 알고리즘이 되는데 탐색을 제외한 오버헤드가 매우 적기 때문이다.

따라서 최선의 경우 O(n)의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2)의 시간복잡도를 갖게 된다.

공간복잡도

주어진 배열 안에서 교환을 통해, 정렬이 수행되므로 O(n)이다.

장점

• 알고리즘이 단순하다.
• 대부분의 원소가 정렬되어있는 경우 매우 효율적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬
• 안정 정렬이다.
• 버블 정렬과 선택 정렬에 비해 빠른 정렬방식이다.

단점

• 시간 복잡도가 최악, 평균 O(n^2)으로 비효율적이다.
• 배열의 길이가 길어질수록 비효율적이다.