डेटा संरचना में अनुकूली विलय और छँटाई

एडेप्टिव मर्ज सॉर्ट

एडेप्टिव मर्ज सॉर्ट सॉर्ट किए गए सब-लिस्ट मर्ज सॉर्ट का मर्जिंग करता है। हालांकि, प्रारंभिक उप-सूची का आकार आकार 1 की उप-सूची होने के बजाय तत्वों की सूची के बीच क्रम के अस्तित्व पर निर्भर करता है। उदाहरण के लिए, चित्र में सूची पर विचार करें।

इसमें 2 क्रमबद्ध उप-सूचियाँ होती हैं।

• 16,15,14,13 तत्वों के साथ उप-सूची 1।
• उप-सूची 2 9,10,11,12 तत्वों के साथ।

उप-सूची 1 को क्रमबद्ध किया गया है लेकिन उल्टे क्रम में। इस प्रकार, उप-सूची 1 को उलट दिया जाता है जैसा कि चित्र में दिखाया गया है।

एक बार उप-सूचियां मिल जाने के बाद विलय की प्रक्रिया शुरू हो जाती है। अनुकूली मर्ज सॉर्ट उप-सूचियों को मर्ज करना प्रारंभ करता है। अनुकूली मर्ज सॉर्ट के लिए केवल एक मर्जिंग चरण की आवश्यकता होगी क्योंकि केवल 2 उप-सूचियां हैं। विलय का परिणाम चित्र में दिखाया गया है।

डिज़ाइन आइडिया

• उन उप-सूचियों को ढूंढकर शुरू करें जो पहले से ही आवश्यक या उल्टे क्रम में क्रमबद्ध हैं
• यदि तत्वों के साथ कोई उप-सूची उल्टे क्रम में मौजूद है, तो उप-सूची को पहले तत्व को अंतिम के साथ, दूसरे तत्व को दूसरे तत्व के साथ बदलकर उल्टा करें और इसे जारी रखा जाता है।
• नई उप-सूचियां बनाने के लिए उप-सूचियां मर्ज करना जारी रखें जब तक कि केवल 1 उप-सूची शेष न हो।

अनुकूली मर्ज सॉर्ट विश्लेषण

आकार 1 की उप-सूची से शुरू होने के बजाय अनुकूली मर्ज सॉर्ट, एक उप-सूची ढूंढता है जो पहले से ही आवश्यक या विपरीत क्रम में क्रमबद्ध है। प्रारंभ में मिली उप-सूचियों का आकार न्यूनतम 2 और अधिकतम m (m तत्वों की संख्या है)।

हालाँकि, यदि उप-सूची में उल्टे क्रम में तत्व हैं, तो यह मर्ज ऑपरेशन शुरू करने से पहले सूची को उलट देता है। सूची को उलटने के लिए (एम/2) विनिमय संचालन की आवश्यकता होती है।

सर्वश्रेष्ठ मामला

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

इस प्रकार सर्वोत्तम मामले के लिए समय जटिलता की गणना इस प्रकार की जाती है -

T(m) = (m-1)+(m/2)
T(m) = (2m-2+m)/2
T(m) = O(m).

हालांकि, अनुकूली मर्ज सॉर्ट मर्ज सॉर्ट की तुलना में O(m) के अतिरिक्त स्थान को लागू करता है

सबसे खराब स्थिति

अनुकूली मर्ज सॉर्ट को उप-सूची मिलेगी जो पहले से ही आवश्यक या रिवर्स ऑर्डर में सॉर्ट की गई है। हालांकि, सबसे खराब स्थिति में आंशिक या कुल आदेश देने वाले तत्व नहीं होते हैं। इस प्रकार, शुरू में मिली उप-सूची 2 आकार की होगी। एक बार उप-सूचियाँ मिल जाने के बाद विलय की प्रक्रिया शुरू हो जाती है।

• आकार 2 की उप-सूचियों को मिलाकर आकार 4 की क्रमबद्ध उप-सूची में परिणाम मिलता है।
• आकार 4 परिणामों की उप-सूचियों को मिलाकर आकार 8 की उप-सूची में क्रमबद्ध किया जाता है।
• विलय की प्रक्रिया 2k

चूंकि अनुकूली मर्ज सॉर्ट के सबसे खराब स्थिति में विलय के चरण मर्ज सॉर्ट के समान हैं। इस प्रकार, अनुकूली मर्ज सॉर्ट की सबसे खराब स्थिति के लिए समय जटिलता मर्ज सॉर्ट के समान है -

T(m) = O(m log m).