बिटोनिक सॉर्टर

बिटोनिक सॉर्ट छँटाई के लिए एक क्लासिक समानांतर एल्गोरिदम है।

बिटोनिक सॉर्ट O(nLog^2n) तुलना करता है।

बिटोनिक सॉर्ट द्वारा की गई तुलनाओं की संख्या मर्ज सॉर्ट [O(nLogn) तुलना] जैसे लोकप्रिय सॉर्टिंग एल्गोरिदम से अधिक है, लेकिन बिटकॉइन सॉर्ट समानांतर कार्यान्वयन के लिए बेहतर है क्योंकि हम हमेशा पूर्वनिर्धारित अनुक्रम में तत्वों की तुलना करते हैं और तुलना का क्रम नहीं करता है। डेटा पर निर्भर हैं। इसलिए यह हार्डवेयर और समानांतर प्रोसेसर सरणी में कार्यान्वयन के लिए उपयुक्त है।

यदि सॉर्ट करने के लिए तत्वों की संख्या 2^n हो तो बिटोनिक सॉर्ट किया जाना चाहिए। बिटोनिक अनुक्रम की प्रक्रिया विफल हो जाती है यदि तत्वों की संख्या ठीक पूर्वोक्त मात्रा में नहीं है।

बिटोनिक अनुक्रम

एक अनुक्रम को बिटोनिक कहा जाता है यदि यह पहले बढ़ रहा है, तो घट रहा है। दूसरे शब्दों में, एक अरैस्ट अरेस्ट [0..n-i] बिटोनिक है अगर कोई इंडेक्स I मौजूद है जहाँ 0 <= i <= n-1 ऐसा है

x0 <= X1… .. <= xi और xi> = xi + 1… ..> = xn-1.

एक क्रम, जो बढ़ते क्रम में क्रमबद्ध है, बिटोनिक को घटते भाग के साथ खाली माना जाता है। इसी तरह, घटते क्रम को बिटोनिक माना जाता है, जो बढ़ते भाग के साथ खाली होता है।
बिटोनिक सीक्वेंस का एक रोटेशन बिटोनिक भी है।

यादृच्छिक इनपुट से बिटोनिक अनुक्रम कैसे बनाएं?

हम लगातार 2-तत्व अनुक्रम से 4-तत्व बिटोनिक अनुक्रम बनाकर शुरू करते हैं। अनुक्रम x0, X1, x2, x3 में 4-तत्व पर विचार करें। हम x0 और X1 को आरोही क्रम में और x2 और x3 को अवरोही क्रम में सॉर्ट करते हैं। हम फिर 4 तत्व बिटोनिक सीक्वेंस बनाने के लिए दो जोड़ों को मिलाते हैं।

अगला, हम दो 4 तत्व बिटोनिक क्रम लेते हैं, एक को आरोही क्रम में, दूसरे को अवरोही क्रम में (बिटोनिक सॉर्ट का उपयोग करते हैं, जिसके बारे में हम नीचे चर्चा करेंगे), और इसी तरह, जब तक हम बिटोनिक अनुक्रम प्राप्त नहीं कर लेते।

उदाहरण:

चरण 1: प्रत्येक 2-निरंतर तत्वों को बिटोनिक अनुक्रम के रूप में विचार करें और प्रत्येक 2- जोड़ी तत्वों पर बिटोनिक सॉर्ट लागू करें। अगले चरण में, दो 4 तत्व बिटोनिक क्रम और इतने पर ले लो।

चरण 2: दो 4 तत्व बिटोनिक क्रम: A (3,7,8,4) और B (2,6,5,1) 2 की तुलना में लंबाई के साथ

इस चरण के बाद, हमें लंबाई 8 का बिटोनिक अनुक्रम मिलेगा।

3, 4, 7, 8, 6, 5, 2, 1

बिटोनिक छँटाई

इसमें मुख्य रूप से दो चरण शामिल हैं।

एक बिटोनिक अनुक्रम बनाना (विस्तार से ऊपर चर्चा की गई)। इस चरण के बाद हम नीचे आरेख में चौथे चरण पर पहुंचते हैं, अर्थात, सरणी {3, 4, 7, 8, 6, 5, 2, 1} बन जाती है।
बिटोनिक अनुक्रम से एक क्रमबद्ध अनुक्रम बनाना: पहले चरण के बाद, पहले आधे को बढ़ते क्रम में और दूसरे आधे को घटते क्रम में क्रमबद्ध किया जाता है। हम पहले छमाही के पहले तत्व की दूसरी छमाही के पहले तत्व के साथ तुलना करते हैं, फिर पहले छमाही के दूसरे तत्व के दूसरे तत्व के साथ और इसी तरह। हम तत्वों का आदान-प्रदान करते हैं यदि पहली छमाही का एक तत्व छोटा है। उपरोक्त तुलना और विनिमय चरणों के बाद, हमें सरणी में दो बिटोनिक क्रम मिलते हैं। नीचे दिए गए चरण को आरेख में देखें। पांचवें चरण में, हमारे पास {3, 4, 2, 1, 6, 5, 7, 8} है। यदि हम तत्वों पर करीब से नज़र डालते हैं, तो हम यह नोटिस कर सकते हैं कि लंबाई n / 2 के दो बिटोनिक क्रम हैं जैसे कि प्रथम बिटनिक अनुक्रम में सभी तत्व {3, 4, 2, 1} दूसरे बिटोनिक अनुक्रम के सभी तत्वों से छोटे हैं {6, 5, 7, 8}। हम दो बिटोनिक अनुक्रमों के भीतर एक ही प्रक्रिया को दोहराते हैं और हमें लंबाई n / 4 के चार बिटोनिक अनुक्रम मिलते हैं जैसे कि बाईं ओर के सभी बिटोनिक सीक्वेंस छोटे और राइट के सभी तत्व हैं। नीचे दिए गए चरण को आरेख में देखें, सरणियाँ {2, 1, 3, 4, 6, 5, 7, 8} हैं। यदि हम इस प्रक्रिया को एक और बार दोहराते हैं, तो हमें आकार n / 8 के 8 बिटोनिक क्रम मिलते हैं, जो 1. है क्योंकि इन सभी बिटोनिक अनुक्रमों को क्रमबद्ध किया गया है और प्रत्येक बिटोनिक अनुक्रम में एक तत्व है, हमें क्रमबद्ध सरणी मिलती है।

बिटोनिक सॉर्ट का विश्लेषण

लंबाई n / 2 के दो क्रमबद्ध अनुक्रमों से लंबाई n का एक क्रमबद्ध क्रम बनाने के लिए, log(n) तुलना की आवश्यकता होती है (उदाहरण के लिए: log आकार जब log2(8) = 3 होता है। इसलिए, तुलनाओं की संख्या T (n) है। संपूर्ण सॉर्टिंग इसके द्वारा दी गई है:

T(n) = log(n) + T(n/2)

इस पुनरावृत्ति समीकरण का हल है

T(n) = log(n) + log(n)-1 + log(n)-2 + … + 1 = log(n) · (log(n)+1) / 2

के रूप में, छँटाई नेटवर्क के प्रत्येक चरण में n / 2 तुलनित्र होते हैं। इसलिए कुल? (एन log^2n) तुलनित्र।

संदर्भ: