बिटोनिक सॉर्ट एक समानांतर सॉर्टिंग एल्गोरिदम है जो सर्वोत्तम कार्यान्वयन के लिए बनाया गया है और हार्डवेयर और समानांतर प्रोसेसर सरणी के साथ इष्टतम उपयोग है। ।
मर्ज सॉर्ट की तुलना में यह सबसे प्रभावी नहीं है। लेकिन यह समानांतर कार्यान्वयन के लिए अच्छा है। यह पूर्वनिर्धारित तुलना अनुक्रम के कारण है जो तुलना को सॉर्ट किए जाने वाले डेटा से स्वतंत्र बनाता है।
बिटोनिक सॉर्ट के प्रभावी ढंग से काम करने के लिए तत्वों की संख्या एक विशिष्ट प्रकार की मात्रा में होनी चाहिए यानी क्रम 2^n ।
बिटोनिक प्रकार का एक प्रमुख भाग बिटोनिक अनुक्रम है जो एक अनुक्रम है जिसके तत्वों का मूल्य पहले बढ़ता है और फिर घटता ।
बिटोनिक अनुक्रम एक सरणी गिरफ्तारी है [0 ... (एन -1)] यदि 0 से n-1 की सीमा के भीतर कोई अनुक्रमणिका मान है। जिसके लिए arr[i] का मान सरणी में सबसे बड़ा होता है। यानी
arr[0] <= arr[1] … <= arr[i] and arr[i] >= arr[i+1] … >= aar[n-1]
बिटोनिक अनुक्रम के विशेष लक्षण -
-
बिटोनिक अनुक्रम को वापस बिटोनिक अनुक्रम में घुमाया जा सकता है।
-
बढ़ते और घटते क्रम में तत्वों के साथ अनुक्रम एक बिटोनिक अनुक्रम है।
बिटोनिक अनुक्रम बनाना
बिटोनिक अनुक्रम बनाने के लिए, हम दो उप-अनुक्रम बनाएंगे, एक आरोही तत्वों के साथ और दूसरा अवरोही तत्वों के साथ।
उदाहरण के लिए, आइए क्रम को arr[] देखें और निम्न अनुक्रम को बिटोनिक अनुक्रम में बदलें।
arr[] = {3, 4, 1, 9, 2, 7, 5, 6} सबसे पहले, हम तत्वों के जोड़े बनाएंगे और फिर इनका एक बिटोनिक अनुक्रम इस तरह से बनाएंगे कि एक आरोही क्रम में हो और दूसरा अवरोही क्रम में हो और इसी तरह।
हमारे सरणी के लिए, बिटोनिक क्रम में जोड़े बनाते हैं।
arr[] = {(3, 4), (1, 9), (2, 7), (5, 6)}
// creating bitonic sequence pairs…
arr[] = {(3, 4), (9, 1), (2, 7), (6, 5)} फिर, हम इन जोड़ियों के जोड़े बनाएंगे। यानी 4 तत्व बिटोनिक अनुक्रम और तत्वों की तुलना 2 दूरी के साथ करते हैं [अर्थात। मैं i+2 के साथ]।
arr[] = {(3, 4, 9, 1), (2, 7, 6, 5)} पहले सेट में आरोही बिटोनिक −
. के रूप में बनाया जाएगा(3, 4, 9, 1) : comparing two distant elements. (3, 1, 9, 4) : Now, check adjacent elements. (1, 3, 4, 9) -> ascending bitonic sequence.
दूसरे सेट में अवरोही बिटोनिक को −
. के रूप में बनाया जाएगा(2, 7, 6, 5) : comparing two distant elements. (6, 7, 2, 5) : Now, check adjacent elements. (7, 6, 5, 2) -> descending bitonic sequence.
अंत में, हमें आकार 8 का बिटोनिक अनुक्रम मिलेगा।
1, 3, 4, 9, 7, 6, 5, 2
अब, चूंकि हमने बिटोनिक अनुक्रम के बारे में सीखा है। हम बिटोनिक सॉर्टिंग . के बारे में जानेंगे ।
बिटोनिक सॉर्टिंग
इन चरणों का उपयोग करके बिटोनिक सॉर्टिंग का उपयोग करके बिटोनिक अनुक्रम को सॉर्ट करने के लिए -
चरण 1 - एक बिटोनिक अनुक्रम बनाएं।
चरण 2 - अब, हमारे पास एक बिटोनिक अनुक्रम है जिसमें एक भाग बढ़ते क्रम में और दूसरा घटते क्रम में है।
चरण 3 - हम दोनों हिस्सों के पहले तत्वों की तुलना और अदला-बदली करेंगे। फिर उनके लिए दूसरा, तीसरा, चौथा तत्व।
चरण 4 - हम अनुक्रम के हर दूसरे तत्व की तुलना और अदला-बदली करेंगे।
चरण 5 - अंत में, हम अनुक्रम के आसन्न तत्वों की तुलना और अदला-बदली करेंगे।
चरण 6 - सभी स्वैप के बाद, हमें सॉर्ट किया गया ऐरे मिलेगा।
उदाहरण
बिटोनिक सॉर्ट के कार्यान्वयन को दिखाने के लिए कार्यक्रम -
#include<iostream>
using namespace std;
void bitonicSeqMerge(int a[], int start, int BseqSize, int direction) {
if (BseqSize>1){
int k = BseqSize/2;
for (int i=start; i<start+k; i++)
if (direction==(a[i]>a[i+k]))
swap(a[i],a[i+k]);
bitonicSeqMerge(a, start, k, direction);
bitonicSeqMerge(a, start+k, k, direction);
}
}
void bitonicSortrec(int a[],int start, int BseqSize, int direction) {
if (BseqSize>1){
int k = BseqSize/2;
bitonicSortrec(a, start, k, 1);
bitonicSortrec(a, start+k, k, 0);
bitonicSeqMerge(a,start, BseqSize, direction);
}
}
void bitonicSort(int a[], int size, int up) {
bitonicSortrec(a, 0, size, up);
}
int main() {
int a[]= {5, 10, 51, 8, 1, 9, 6, 22};
int size = sizeof(a)/sizeof(a[0]);
printf("Original array: \n");
for (int i=0; i<size; i++)
printf("%d\t", a[i]);
bitonicSort(a, size, 1);
printf("\nSorted array: \n");
for (int i=0; i<size; i++)
printf("%d\t", a[i]);
return 0;
} आउटपुट
Original array: 5 10 51 8 1 9 6 22 Sorted array: 1 5 6 8 9 10 22 51