Sắp xếp Chèn nhị phân là một kiểu đặc biệt của sắp xếp Chèn sử dụng thuật toán tìm kiếm nhị phân để tìm ra vị trí chính xác của phần tử được chèn trong mảng.
Sắp xếp chèn là kỹ thuật sắp xếp hoạt động bằng cách tìm vị trí chính xác của phần tử trong mảng và sau đó chèn phần tử đó vào đúng vị trí của nó.
Tìm kiếm nhị phân là kỹ thuật tìm kiếm hoạt động bằng cách tìm giữa mảng để tìm phần tử.
Vì độ phức tạp của tìm kiếm nhị phân là thứ tự logarit, nên độ phức tạp về thời gian của thuật toán tìm kiếm cũng sẽ giảm xuống theo thứ tự logarit.
Thực hiện sắp xếp Chèn nhị phân. chương trình này là một chương trình sắp xếp chèn đơn giản nhưng thay vì kỹ thuật tìm kiếm tiêu chuẩn, tìm kiếm nhị phân được sử dụng.
Ví dụ
#include <iostream>
using namespace std;
int binarySearch(int arr[], int item, int low, int high) {
if (high <= low)
return (item > arr[low])? (low + 1): low;
int mid = (low + high)/2;
if(item == arr[mid])
return mid+1;
if(item > arr[mid])
return binarySearch(arr, item, mid+1, high);
return binarySearch(arr, item, low, mid-1);
}
void BinaryInsertionSort(int arr[], int n) {
int i, loc, j, k, selected;
for (i = 1; i < n; ++i) {
j = i - 1;
selected = arr[i];
loc = binarySearch(arr, selected, 0, j);
while (j >= loc) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = selected;
}
}
int main() {
int arr[] = {12, 56, 1, 67, 45, 8, 82, 16, 63, 23};
int n = sizeof(arr)/sizeof(arr[0]), i;
BinaryInsertionSort(arr, n);
cout<<"Sorted array is : \n";
for (i = 0; i < n; i++)
cout<<arr[i]<<"\t";
return 0;
} Đầu ra
Sorted array is : 1 8 12 16 23 45 56 63 67 82