이진 삽입 정렬(Binary Insertion Sort)

삽입 정렬이란?

• 배열에서 인덱스 i를 증가시키며 왼쪽의 정렬된 곳에 array[i]가 들어갈 위치를 찾아서 삽입하는 방식의 정렬

이진 삽입 정렬이란?

• 삽입 정렬에서 array[i]가 들어갈 위치를 이진 검색(Binary Search)을 이용해 찾는다.

Pseudo-code

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

binary_search_upper_bound(start_pos, end_pos, key) {
    while(start_pos < end_pos) {
    	m = (start_pos + end_pos)/2
    	if(k >= val[m]) start_pos = m+1
        else end_pos = m
    }
    return end_pos // start_pos와 end_pos 사이에서 val[i] > k 가 처음 되는 i값을 return
}

소스코드

//[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;	
  }  	
}

참고

https://m.blog.naver.com/PostView.nhn?blogId=rhaosoversan&logNo=221377149974&proxyReferer=https:%2F%2Fwww.google.com%2F