বাইনারী সন্নিবেশ বাছাই সন্নিবেশ সাজানোর একটি বিশেষ প্রকার যা অ্যারেতে সন্নিবেশিত উপাদানটির সঠিক অবস্থান খুঁজে বের করতে বাইনারি অনুসন্ধান অ্যালগরিদম ব্যবহার করে৷
সন্নিবেশ বাছাই হল সাজানোর কৌশল যা অ্যারেতে উপাদানটির সঠিক অবস্থান খুঁজে বের করে এবং তারপরে এটিকে সঠিক অবস্থানে ঢোকানোর মাধ্যমে কাজ করে৷
বাইনারী অনুসন্ধান এটি অনুসন্ধানের কৌশল যা উপাদান খুঁজে পাওয়ার জন্য অ্যারের মাঝখানে খুঁজে বের করে কাজ করে।
যেহেতু বাইনারি অনুসন্ধানের জটিলতা লগারিদমিক ক্রম অনুসারে, অনুসন্ধানের অ্যালগরিদমের সময় জটিলতাও লগারিদমিক ক্রমে হ্রাস পাবে৷
বাইনারি সন্নিবেশ সাজানোর বাস্তবায়ন। এই প্রোগ্রামটি একটি সাধারণ সন্নিবেশ বাছাই প্রোগ্রাম কিন্তু স্ট্যান্ডার্ড অনুসন্ধান কৌশলের পরিবর্তে বাইনারি অনুসন্ধান ব্যবহার করা হয়৷
উদাহরণ
#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
