Sắp xếp chèn nhị phân là loại đặ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 vị trí chính xác của phần tử chèn vào 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í đúng của phần tử trong mảng và chèn nó vào vị trí đó.
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à bậc logarit, độ phức tạp thời gian của thuật toán tìm kiếm cũng giảm xuống bậc logarit.
Triển khai sắp xếp chèn nhị phân. Chương trình này là sắp xếp chèn đơn giản nhưng thay vì kỹ thuật tìm kiếm chuẩn, dùng tìm kiếm nhị phân.
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<<"Mảng đã sắp xếp: \n";
for (i = 0; i < n; i++) cout<<arr[i]<<"\t";
return 0;
}
Kết quả
Mảng đã sắp xếp: 1 8 12 16 23 45 56 63 67 82