การเรียงลำดับการแทรกไบนารี เป็นการเรียงลำดับการแทรกแบบพิเศษซึ่งใช้อัลกอริธึมการค้นหาแบบไบนารีเพื่อค้นหาตำแหน่งที่ถูกต้องขององค์ประกอบที่แทรกในอาร์เรย์
การเรียงลำดับการแทรกเป็นเทคนิคการเรียงลำดับที่ทำงานโดยการค้นหาตำแหน่งที่ถูกต้องขององค์ประกอบในอาร์เรย์แล้วแทรกลงในตำแหน่งที่ถูกต้อง
การค้นหาไบนารี เป็นเทคนิคการค้นหาที่ทำงานโดยการหาค่ากลางอาร์เรย์เพื่อค้นหาองค์ประกอบ
เนื่องจากความซับซ้อนของการค้นหาแบบไบนารีเป็นลำดับลอการิทึม ความซับซ้อนของเวลาของอัลกอริทึมการค้นหาก็จะลดลงเป็นลำดับลอการิทึมด้วย
การใช้งานการเรียงลำดับการแทรกไบนารี โปรแกรมนี้เป็นโปรแกรมจัดเรียงการแทรกแบบธรรมดา แต่แทนที่จะใช้เทคนิคการค้นหาแบบมาตรฐานในการค้นหาแบบไบนารี
ตัวอย่าง
#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;
} ผลลัพธ์
Sorted array is : 1 8 12 16 23 45 56 63 67 82
