Binary Insertion sort เป็นประเภทพิเศษของ Insertion sort ที่ใช้อัลกอริทึมค้นหาแบบทวิภาคเพื่อหาตำแหน่งที่ถูกต้องของสมาชิกที่แทรกในอาร์เรย์
Insertion sort เป็นเทคนิคการเรียงลำดับที่ทำงานโดยการหาตำแหน่งที่ถูกต้องของสมาชิกในอาร์เรย์ และแทรกมันเข้าไปในตำแหน่งที่ถูกต้องนั้น
Binary search เป็นเทคนิคการค้นหาที่ทำงานโดยการหาจุดกลางของอาร์เรย์เพื่อหาสมาชิก
เนื่องจากความซับซ้อนของ binary search เป็นออเดอร์ลอการิทึม อัลกอริทึมการค้นหาจะมีความซับซ้อนด้านเวลาลดลงเป็นออเดอร์ลอการิทึมเช่นกัน
การนำไปใช้ของ Binary Insertion sort โปรแกรมนี้เป็นโปรแกรม Insertion sort ธรรมดา แต่แทนที่จะใช้เทคนิคค้นหามาตรฐาน ใช้ binary search แทน
ตัวอย่าง
#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
