이진 삽입 정렬(Binary Insertion Sort)

자 제목 부터 삽입 정렬이 나온다. 그럼 기본적으로 삽입 정렬에 대한 지식이 필요하지 않을까?

한번 보고 왔으면 좋겠당 

삽입정렬

삽입 정렬(Insertion Sort)

 

앞서 봤던 삽입정렬은 선형탐색을 통한 원소가 들어갈 위치를 잡았다.

 

하지만 이진 삽입 정렬은 다르다. 이진 탐색(Binary Search)을 이용해 보자

 

천천히 생각해보자 저 위에 삽입 정렬은 target으로 숫자를 설정하고 그 숫자를 맞는 위치를 찾기위해 반복을 계속했다

이게 무슨 문제인가? 당연한거 아닌가? 그렇긴한데. 한 원소의 작업시간이 최대 N번 일어난다.

 

그래서 이진 탐색이 중요한것이다. 이건 무려 logN의 시간 복잡도를 갖는다.

완전 혹하지 않는가??? 한번 알아보자

---

알아봤다면 다시 이진 삽입 정렬을 알아보기 전에 우선 삽입 정렬의 코드를 한번 더 보도록 하자

void insertionSort(int[] arr, int size) {
    for(int i = 1; i < size; i++) {
        int target = arr[i];
    	int j = i - 1;
 
        while(j >= 0 && target < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
 
        arr[j + 1] = target;	
	}
}

삽입정렬에서 말한대로 while문에서 j>=0과 target <a[j]의 두조건이 계속해서 반복되고 

1.  j >= 0 은 비교 가능한 최대 하한 인덱스인 0까지 탐색

2. target < arr[j] 는 target이 계속 탐색을 진행하며 target보다 작을때까지 반복한다.

계에에속 반복한다.

 

 

그럼 이진 삽입 코드는 얼마나 편해진걸까?

void insertionSort(int[] arr, int size) {
    for(int i = 1; i < size; i++) {
        int target = arr[i];
        int location = binarySearch(arr, 0, i, target);
        
        int j = i - 1;
        while(j >= location) {
            arr[j + 1] = arr[j];
            j--;
        }
        a[location] = target;
    }
}

삽입정렬의 코드가 별로 큰 차이는 없다 그림으로 봐도 별 차이 없다. 하지만 엄연히 다른 방식인 것이다.

1. 현재 타겟이 되는 숫자에 대해 이전 위치에 있는 원소들에 들어 갈 위치를 이분 탐색을 통해 얻어낸다.
2. 들어가야 할 위치를 비우기 위해 후방 원소들을 한칸 씩 밀고 비운 공간에 타겟을 삽입한다.
3. 그것을 반복한다.

그럼 이제 두개를 합쳐보도록 하자

public class BinaryInsertionSort {
    public static void binaryInsertionSort(int[] arr) {
        binaryInsertionSort(a, a.length);
    }
    private static void binaryInsertionSort(int[] arr, int size) {
        for(int i = 1; i < size; i++) {
            int target = arr[i];
            int location = binarySearch(arr, target, 0, i);
            
            int j = i - 1;
            
            while(j >= location) {
                arr[j + 1] = arr[j];
                j--;
            }
            
            a[location] = target;
        }
    }
    private static int binarySearch(int[] arr, int key, int low, int high) {
        int mid;
        while( low < high ) {
            mid = high + low / 2;
            if(key < arr[mid]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return high;
    }
}

이 구현에서 뭔가 이상한게 있다. 아까 이진 탐색이라고 적어놓은 코드와 조금 다르다.

그 이유는 이번 코드에 작성한 코드는 찾는 코드가 아니라 집어넣는 코드이기 때문이다. 그렇다고 이해가 어려워졌다 이런건 아니니까 한번 읽어보는게 좋다.

이런식으로 이분 삽입 정렬이 이루어지는것이다.

 

---

자! 이제 삽입정렬과 이진 삽입 정렬을 비교해보았다.

조금 충격적인것은 두개 다 시간 복잡도는 O(N2)을 가는다는 것이다.

왜냐하면 결국 탐색과 시프팅(스왑)을 하는것은 똑같기 때문이다.

 

 

두개의 차이는 두가지의 일을 같이했냐 나눠서 하냐의 차이이다.

삽입정렬은 탐색과 시프팅(스왑) 를 동시에 한다.

이진 삽입정렬은 이분 탐색 따로 시프팅(스왑)을 따로 진행한다.

이 두가지는 생각보다 큰 차이다.

 

우리는 지금까지 단순한 배열 하나로 비교를 반복했다. 하지만 비교 대상자가 많아진다면? 그럼 말이 달라진다.

우린 이진 삽입정렬에서 탐색을 이진탐색으로 사용하고 이진 탐색 자체의 시간 복잡도는 O(logN)이다.

 

삽입정렬은 비교 탐색을 하는데 걸리는 시간 = O(N2)

이진 삽입 정렬은 이진 탐색기법을 사용하기 때문에 탐색시간이 O(logN)에 불과하다.

그럼 탐색에서 걸리는 시간이 완전 차이가 나는것이다

이것이 "비교작업"의 차이이다.

지금 까지 우리는 배열이라는 Int형인 단일 배열을 사용했지만 타입은 다양하다.

※대게 비교작업은 단일타입이 아닌 다양한 변수가 있고 Comparable 혹은 Comparator를 구현한다.

 

만약 다양한 타입의 a,b,c가 있고 그것을 비교해야 한다면 삽입정렬은 모두 N번의 비교를 해야한다.

하지만 이진 삽입 정렬은 logN번의 비교를 하면서 "비교 비용"이 달라진다.

 

결론은, 두개는 굉장히 흡사하지만 비교 타입이 다양해지면 이진 삽입정렬이 조금 더 빠르다는것이다.

이는 이후에 알아볼 TimSort에서 크게 작용하는데 TimSort는 객체를 정렬할때 사용한다. 객채(object)는 다양한 타입이 존재하고 비교 횟수가 증가하면서 오버헤드가 커지니 비교 횟수를 최소화 할 수 있는 이진 삽입 정렬을 사용하게 될것이다.

 

이진 삽입 정렬의 장단점

◐장점 = 1. 추가적인 메모리 소비가 작다.

               2. 비교비용이 비싸지면 삽입 정렬에 비해 빠르다.

               3. 안정 정렬이 가능하다.

               4. 추가 구현을 통해 최상의 경우 O(N)까지도 빨라진다.

◑단점 = 1. 삽입정렬보다 무조건 빠르다고 할수없다.

               2. 평균 시간 복잡도는 삽입정렬과 동일하게 O(N2)이다.

 

두개의 시간 복잡도차이

삽입 정렬(Insertion Sort)
Best = O(N2)
Worst = O(N2)

이진 삽입 정렬(Binary Insertion Sort)
Best = O(N)
Worst = O(N2)

---

어렵다...진짜루

다음에는 Binary Insertion Sort를 좀 더 심화해서 더 빠르게 적립하게 만드는 식을 만들어 보겠다.