[정렬] 이진 삽입 정렬

 

이진 삽입 정렬

삽입정렬의 메커니즘은 같으나, 원소가 들어 갈 위치를 선형 탐색이 아닌 이분 탐색(이진 탐색)을 이용한 방법으로 구현한다.

일단 이분 탐색 과정을 이해해보자면, '정렬 된 상태의 구간' 내에서 중간에 위치한 원소와 비교하여 중간 원소보다 작다면 왼쪽 구간으로, 크다면 오른쪽 구간으로 다시 나누어 탐색하는 과정을 말한다.

쉽게 그림으로 이해하자면 다음과 같다.

기존의 삽입정렬은 while()문으로 한 번 순회했고, 이진 삽입 정렬은 이분탐색 과정과 원소들을 밀기 위한 순회 과정을 거쳐야 하는데, 오히려 이진 삽입 정렬이 느린 것이 아닌가?

기본적으로 Insertion Sort나, Binary Insertion Sort나 N개의 각 원소들은 삽입시 N개의 원소를 밀어내는 시프트 작업이 발생하기 때문에 O(N2) 의 시간 복잡도를 갖는 것은 같다.

그리고 위에서 말했던 것처럼 while문으로 한 번 순회하는 일반적인 Insertion Sort가 별도의 이진탐색 과정을 거친 뒤 얻은 위치에 원소를 삽입하기 위한 시프트 작업이 발생하는 Binary Insertion Sort보다 빠르게 보이기도 한다.

그러면 왜 이진 삽입 정렬이 필요한 것인가? 이를 이해하기 위해서는 이분 탐색부터 이해해야 한다.

이분 탐색 자체는 앞서 설명했듯, 탐색 비용이 O(logN)의 시간 복잡도를 갖는다. 그리고 우리는 이진 삽입 정렬에서 원소가 들어갈 위치를 찾는 비교작업으로 사용을 하고 있다.

즉, 일반적인 삽입 정렬과의 차이라면 삽입 정렬은 탐색과 시프팅 작업을 동시에 하지만, 이진 삽입 정렬은 탐색을 이분 탐색으로 따로 구한 뒤 시프팅 작업을 거친다.

그럼 이진 삽입 정렬이 빠른 경우는 어떤 경우일까?

바로 '비교 작업 비용'이 '시프팅(스왑) 비용'보다 클 때 이진 삽입 정렬이 좀 더 빠르다는 것이다.

간단한 숫자같은 단일 비교는 비교비용이 적기 때문에 일반 삽입정렬이 빠르지만, 복잡한 객체들 간의 비교를 해야한다면 비교비용은 많아지게 되고, 비교적 삽입 정렬에 비해 비교 연산이 최소화된 이진삽입정렬이 좀더 빠르다.

public class BinaryInsertionSort {

    public static void binaryInsertionSort(int[] a) {
        binaryInsertionSort(a, a.length);
    }

    private static void binaryInsertionSort(int[] a, int size) {
        for(int i = 1; i < size; i++) {
            // 타겟 넘버
            int target = a[i];

            // 이분탐색을 통해 target이 들어가야 할 위치를 얻는다.
            int location = binarySearch(a, target, 0, i);

            int j = i - 1;

            // 시프팅 작업
            while(j >= location) {
                a[j + 1] = a[j];    // 이전 원소를 한 칸씩 뒤로 미룬다.
                j--;
            }

            a[location] = target;    
        }
    }

    // 이분 탐색
    private static int binarySearch(int[] a, int key, int lo, int hi) {

        int mid;
        while(lo < hi) {
            // 좀 더 빠르게 하기 위해서 /2 대신 >>> 1을 사용해도 된다. 
            mid = lo + ((hi - lo) / 2);
			//오름차순
            //if (arr[mid]<key){
            //내림차순
            if(key < a[mid]) {
                hi = mid;
            }
            else {
                lo = mid + 1;
            }
        }
        return hi;
    }

}

 

장점

1. 추가적인 메모리 소비가 작다.
2. 비교 비용이 비싸질 수록 삽입 정렬에 비해 빨라진다.
3. 안장정렬이 가능하다.
4. 추가 구현을 통해 최상의 경우 O(N)의 시간복잡도를 갖게 된다.

단점

1. 항상 삽입정렬보다 빠른 것은 아니다.
2. 평균 시간 복잡도는 삽입정렬과 동일하게 O(N2) 이다.

 

 

 

 

출처:

https://st-lab.tistory.com/179