[자료구조] 이진삽입정렬(BinaryInsertionSort)

[이진삽입정렬]

 

 

이진삽입정렬은 삽입정렬과 메커니즘은 똑같지만 삽입위치를 이진탐색(BinarySearch) 으로 찾는다.

 

원소가 들어 갈 위치를 선형 탐색이 아닌 이분 탐색(이진탐색)을 이용한 방법으로 구현한다.

 

일반적인 삽입정렬은 선형 탐색이다보니 한 원소에 대해 비교 작업이 최대 N번이 일어난다. 

 

하지만 이진삽입정렬은 탐색 과정을 이분탐색을 통해 log2n의 탐색시간복잡도를

갖도록 하기 때문에 비교연산횟수가 줄어든다!

 

---

[BinarySearch]

 

int BinarySearch(int arr[], int left, int right, int target) {
	
	// 종료부분
	if (right - left == 1) {
		if (target > arr[left]) return right;
		else return left;
	}
	
	int mid = (left + right) / 2;

	if (target > arr[mid]) {
		return BinarySearch(arr, mid, right, target);
	}
	// target < arr[mid]
	else {
		return BinarySearch(arr, left, mid, target);
	}
}

 

일반적인 BinarySearch와는 다른 목적의 함수를 구현해보았다.

일반 BS는 target값의 idx를 반환하는 역할이지만

여기서의 BS의 목적은 target값이 들어갈 위치 idx를 반환하는 것이다.

따라서 종료부분이 다르다.

 

---

[BInsertionSort]

void BInsertionSort(int arr[],int len) {
	for (int i = 1; i < len; i++) {
		int temp = arr[i];
		int location = BinarySearch(arr, 0, i, temp);
		
		for (int k = i-1; k >=location; k--) {
			arr[k + 1] = arr[k];
		}
		arr[location] = temp;
	}
}

 

---

[main]

int main() {
	int arr[SIZE] = { 5,8,1,4,2,6,10,9,3,7 };
	BInsertionSort(arr,SIZE);
	return 0;
}

 

---

 

차례대로 잘 정렬되어 나온다

과정도 출력되게 하였다.

내려갈때마다 한 개씩 더 정렬되고 있다.

출력되는 걸 보면 일반 삽입정렬과 동일한 결과지만

삽입위치를 이진탐색으로 찾는다는게 차이점이다