बिटोनिक सॉर्ट एक समानांतर सॉर्टिंग एल्गोरिदम है जिसे सर्वोत्तम कार्यान्वयन के लिए बनाया गया है और हार्डवेयर और समानांतर प्रोसेसर सरणी के साथ इष्टतम उपयोग है।
यह मर्ज सॉर्ट की तुलना में सबसे प्रभावी नहीं है। लेकिन यह समानांतर कार्यान्वयन के लिए अच्छा है। यह पूर्वनिर्धारित तुलना अनुक्रम के कारण है जो तुलना को उन डेटा से स्वतंत्र बनाता है जिन्हें क्रमबद्ध किया जाना है।
बिटोनिक सॉर्ट के प्रभावी ढंग से काम करने के लिए तत्वों की संख्या एक विशिष्ट प्रकार की मात्रा में होनी चाहिए यानी क्रम 2^n।
बिटोनिक सॉर्ट का एक प्रमुख हिस्सा बिटोनिक अनुक्रम है जो एक ऐसा अनुक्रम है जिसके तत्वों का मान पहले बढ़ता है और फिर घटता है।
बिटोनिक अनुक्रम एक सरणी arr[0 ... (n-1)] है यदि इंडेक्स मान i की रेंज 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)} // बिटोनिक अनुक्रम जोड़े बनाना...
arr[] = {(3, 4), (9, 1), (2, 7), (6, 5)}
फिर, हम इन जोड़ों के जोड़े बनाएंगे। यानी 4 तत्वों का बिटोनिक अनुक्रम और 2 दूरी पर स्थित तत्वों की तुलना करें [यानी i के साथ i+2]।
arr[] = {(3, 4, 9, 1), (2, 7, 6, 5)}
पहले सेट में आरोही बिटोनिक बनेगा -
(3, 4, 9, 1) : दो दूर के तत्वों की तुलना। (3, 1, 9, 4) : अब, आसन्न तत्वों की जांच करें। (1, 3, 4, 9) -> आरोही बिटोनिक अनुक्रम।
दूसरे सेट में अवरोही बिटोनिक बनेगा -
(2, 7, 6, 5) : दो दूर के तत्वों की तुलना। (6, 7, 2, 5) : अब, आसन्न तत्वों की जांच करें। (7, 6, 5, 2) -> अवरोही बिटोनिक अनुक्रम।
अंत में, हमें आकार 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("मूल सरणी: \n");
for (int i=0; i<size; i++)
printf("%d\t", a[i]);
bitonicSort(a, size, 1);
printf("\nक्रमबद्ध सरणी: \n");
for (int i=0; i<size; i++)
printf("%d\t", a[i]);
return 0;
}
आउटपुट
मूल सरणी: 5 10 51 8 1 9 6 22 क्रमबद्ध सरणी: 1 5 6 8 9 10 22 51
