बाइनरी इंसर्शन सॉर्ट इंसर्शन सॉर्ट का एक विशेष प्रकार है जो ऐरे में डाले गए एलिमेंट की सही स्थिति खोजने के लिए बाइनरी सर्च एल्गोरिदम का उपयोग करता है।
इंसर्शन सॉर्ट एक सॉर्टिंग तकनीक है जो ऐरे में एलिमेंट की सही स्थिति ढूंढकर और फिर उसे उसकी सही स्थिति में डालकर काम करती है।
बाइनरी सर्च एक खोज तकनीक है जो एलिमेंट को खोजने के लिए ऐरे के मध्य को ढूंढकर काम करती है।
चूंकि बाइनरी सर्च की जटिलता लॉगरिदमिक क्रम की होती है, खोज एल्गोरिदम की समय जटिलता भी लॉगरिदमिक क्रम तक घट जाएगी।
बाइनरी इंसर्शन सॉर्ट का कार्यान्वयन। यह प्रोग्राम एक साधारण इंसर्शन सॉर्ट प्रोग्राम है लेकिन मानक खोज तकनीक के बजाय बाइनरी सर्च का उपयोग किया जाता है।
उदाहरण
#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
