004. 이진 삽입 정렬(Binary Insertion Sort)

1. 알고리즘 설명

삽입 정렬을 개선한 알고리즘이다.

삽입 정렬의 경우, i를 증가시키면서 왼편 정렬되어 있는 곳에서 v[i]가 들어갈 곳을 찾아서 집어넣는 작업을 해나가는데, 이때 '정렬되어 있는 곳에서 찾는' 작업을 이진 검색(binary search)로 해서 빠르게 찾는 것이다. 또한, 들어갈 곳을 만들기 위해 값들을 오른쪽으로 한 칸씩 이동시키는데, 이 작업을 하나씩 이동시키는 것이 아니라 블록 전체를 오른쪽으로 한 칸 이동시키면(move 함수 이용), 이론적으로는 교환에 O(n²)이지만 실제 move를 이용한 블록 이동을 하면 O(n)의 효과를 볼 수 있다.

개선 1. 순차 검색에 의해 '비교'에 대한 시간 복잡도 O(n²) --> 이진 검색으로 O(nlogn))으로 개선

개선 2. 값 1개씩 이동으로 '교환'에 대한 시간 복잡도 O(n²) --> 블록 이동으로 O(n) 효과

2. 알고리즘 Flow

binary_insersionSort(v)

1. i=1에서 (n-1)인 동안
2. key=v[i]
3. [0,i]구간에서 key의 upper bound인 위치 p를 이진탐색으로 찾는다
3. [p,i-1]블록을 [p+1,i]블록이 되도록 move
4. v[p]=key

binary_search_upper_bound(s,e,k) //s:start pos, e:end pos, k:the key to find

1. while(s<e) //[s,e)
2. m = (s+e)/2
3. if(k >= v[m]) s=m+1 //[m+1,e) 
4. else          e=m   //(s,m)
5. 1로 돌아감
6. return e

위 binary_search_upper_bound 함수는, [s, e) 사이에서 v[i]>k가 처음 되는 i 값을 리턴한다. (일반적인 이진 탐색은 v[i]==k가 되는 i 값 리턴)

삽입 정렬에서 요구되는 위치가, 원하는 key가 들어갈 자리이기에, 왼쪽에서 오른쪽으로의 순서로 생각했을 때, key보다 큰 수가 처음으로 나오는 자리가 key가 들어갈 자리가 된다.

따라서, 이러한 upper bound 자리를 찾을 수 있게 이진 탐색 코드를 작성해야 한다. 이를 위해서는 (k > = v[m])일 때 중간 m을 기준으로 오른 편을 찾을 수 있게 하고 --> if(k>=v[m]) s=m+1

그렇지 않은 경우 그 왼편을 찾게 하면 된다. --> else e=m

 

3. 소스 코드

//[s,e)사이에서 v[i]>k가 처음되는 i값 리턴
int bi_search_upper_boutn(vector<int> &v, int s, int e, const int k){
  int m;    
  while(s<e){             //[m,e)
    m = (s+e)/2;
    if(k >= v[m]) s=m+1;  //[m+1,e)
    else e=m;              //[s,m)    
  }    
  return e;
}

void binary_insertionSort(vector<int> &v){
  int size = v.size();
  for(int i=1;i<size;++i){    
    int key = v[i];
    int pos = bi_search_upper_boutn(v,0,i, key);    
    move(v.begin()+pos,v.begin()+i,v.begin()+pos+1);
    v[pos] = key;    
  }      
}

위 코드의 binary_insertionSort 함수를 보면, move 함수에 의해 블록 전체를 한 칸 오른 편으로 shift 하는 효과를 보게 한 것을 볼 수 있을 것이다.

이 함수를 사용함으로써 각각 하나씩 '교환' 일어나서 성능 감소를 일으키는 것을 막을 수 있다.

 

4. 시간 복잡도: O(nlogn)

• 비교: O(nlogn)
• 교환: O(n)

i=1 : 비교(log2), 교환(최소0, 최대1)
i=2 : 비교(log3), 교환(최소0, 최대1)
...
i=n-1: 비교(logn), 교환(최소0, 최대1)

총 비교: O(nlogn)
총 교환: O(n)

총 비교 횟수는,

 

출처: https://book.huihoo.com/data-structures-and-algorithms-with-object-oriented-design-patterns-in-c++/html/page491.html

 

 

5. 공간 복잡도: O(n)

 

6. 데이터 안정성: 안정함

(같은 값에 대해 원래의 순서가 정렬 후에도 보존됨)

 

7. 알고리즘 특성

원래의 삽입 정렬은 비교와 교환에 모두 O(n²) 이었으나, 이진 삽입 정렬에 블록 단위 이동을 결합했을 경우에는 비교에 O(nlogn) 삽입에 O(n)으로 개선됨을 알 수 있다.