पिछले लेख में, हम
रिलीफ मर्ज के प्रकारों (मुख्य रूप से ऐतिहासिक रुचि के कारण) से परिचित
हुए । आज क्या चलन है?
विलय के माध्यम से आदेश देने की अवधारणा से खुद को परिचित करने के लिए, आमतौर पर संतुलित मर्ज एल्गोरिदम का उपयोग किया जाता है। शब्द "संतुलन" का अर्थ है कि एल्गोरिथ्म पुनरावृत्ति से सरणी और उसके उप-भागों को लगभग समान भागों में विभाजित करता है। आज हम देखते हैं कि यह व्यवहार में कैसा दिखता है।
कार्यों की एक जोड़ी दोनों विधियों के लिए समान है। वैसे भी, कि "डाउन-अप", कि "अप-डाउन" लगभग समान एल्गोरिथ्म है, बस विभिन्न कोणों से दिखाया गया है।
हमें वास्तव में, एक खंड में खंड के दो हिस्सों के विलय की आवश्यकता है। हिस्सों को एक साथ एक सरणी में क्रमबद्ध किया जाता है, दोनों पुनरावृत्तियों में वर्तमान तत्वों की तुलना की जाती है और छोटा तत्व दूसरे सरणी में जाता है:
एक सेगमेंट को दूसरे एरे से कॉपी करना। दोनों कार्यान्वयन दो सरणियों पर काम करते हैं, डेटा को मुख्य से सहायक और इसके विपरीत तक लगातार चलाना पड़ता है:
अवरोही संतुलित विलय
सबसे पहले, पूरी सरणी ली जाती है, जिसके बाद एक पुनरावर्ती वंश शुरू होता है। जब तक हम एक तत्व (जो स्वयं द्वारा छांटे जाते हैं) की उपग्रहों तक पहुँचने तक एक सरणी को द्विभाजित किया जाता है। फिर पुनरावृत्ति रिवर्स वृद्धि शुरू करती है, रास्ते के साथ सबरेज़ को मिलाती है (जिसका आकार प्रत्येक स्तर पर दोगुना हो जाता है)।
संतुलित उर्जा विलय
यहाँ पर सरणी पर पुनरावृत्ति होती है, जिस तरह से हम पहले पड़ोसी न्यूनतम सरणियों (एक तत्व से) लेते हैं और उन्हें जोड़े में विलय करते हैं। प्रत्येक चरण में सॉर्ट किए गए सबरेज़ को दोगुना करने के बाद, हम पड़ोसियों को फिर से मर्ज करते हैं और तब तक जारी रखते हैं जब तक कि हम आउटपुट पर सॉर्ट किए गए फॉर्म में पूरे सरणी नहीं प्राप्त करते हैं।
सामान्य तौर पर, एक टॉप-डाउन कार्यान्वयन बेहतर होता है, क्योंकि यह दो सरणियों का अधिक कुशलता से उपयोग करता है, जो कि बस "मुख्य या सहायक" की भूमिकाओं को लगातार बदलते हैं। अपस्ट्रीम संस्करण में, सरणी A हमेशा प्राथमिक होती है, और सरणी B हमेशा सहायक होती है। नतीजतन, प्रत्येक पुनरावृत्ति के बाद, बी से डेटा को पूर्ण रूप से ए में वापस किया जाना चाहिए, जो एल्गोरिथम जटिलता के सुधार में योगदान नहीं करता है। दूसरी ओर, आरोही का कार्यान्वयन सरल है, इसमें पुनरावृत्ति भी नहीं होती है।
असंतुलित विलय
"संतुलन" शब्द से ही यह किसी प्रकार की विश्वसनीयता, स्थायित्व को प्रभावित करता है। आपको यह भी आभास हो सकता है कि एक अच्छा एल्गोरिथ्म संतुलित होना चाहिए। और "असंतुलन" कुछ प्रकार की अस्थिरता और विकृतियों के साथ जुड़ा हुआ है। ठीक है, वास्तव में, एक
संतुलित एक
असंतुलित की तुलना में सभी मामलों में बेहतर नहीं होना चाहिए?
वास्तव में, यह बदतर है। बेशक, सबरेज़ को बराबर हिस्सों में विभाजित करना (जो कि मर्ज प्रकारों के लिए संतुलन का मतलब है) को लागू करना बहुत आसान है। अपने आप को सरणी को आधे में विभाजित करें और प्रत्येक आधे पर पुनरावृत्ति लागू करें। दरअसल, यह सहज असंतुलित होने से पहले संतुलित विलय का मुख्य लाभ है।
निम्नलिखित प्रकाशनों में, हम असंतुलित तरीकों को देखेंगे। उन्हें समझना और लागू करना अधिक कठिन है। बाद के विलय के लिए डेटा समान रूप से और समान रूप से सहायक सरणियों में वितरित नहीं किया जाएगा, लेकिन सामान्यीकृत फाइबोनैचि संख्याओं के अनुसार। और यह आपको शक्तिशाली परिणाम प्राप्त करने की अनुमति देगा जो सरल संतुलित तरीकों के लिए अप्राप्य हैं।
संदर्भ
मर्ज (
Google-Translate ),
मर्जश्रृंखला लेख:
अगले मर्ज सॉर्टिंग अब एल्गोलाब एप्लिकेशन में उपलब्ध हैं (उन लोगों के लिए जो इस एक्सेल एप्लिकेशन का उपयोग करके एल्गोरिदम का अध्ययन करते हैं, फ़ाइल को अपडेट करते हैं)।
ऐरे अस्थायी रूप से सीमित हैं - उनका आकार दो की शक्ति होना चाहिए (प्रोग्रामिंग विज़ुअलाइज़ेशन के दौरान कुछ कठिनाइयों के कारण)। थोड़ी देर बाद किसी भी सरणियों को छांटना संभव होगा।
यह लेख EDISON सॉफ्टवेयर, एक कंपनी के समर्थन के साथ लिखा गया था जो एम्बेडेड सॉफ़्टवेयर बनाने और जावा पर मोबाइल एप्लिकेशन विकसित करने के लिए क्लाउड सेवाओं का उपयोग करती है।