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