Python Merge Sort Tutorial

डेटा को सॉर्ट करना डेटा पेशेवरों द्वारा अपने दैनिक कार्य में किए जाने वाले सबसे सामान्य कार्यों में से एक है। कई बार हमें सार्थक जानकारी निकालने के लिए डेटा को किसी विशेष क्रम में प्रदर्शित करने की आवश्यकता होती है। सौभाग्य से, आजकल हमें यह काम मैन्युअल रूप से नहीं करना पड़ता। कंप्यूटर यह जादू हमारे लिए अद्वितीय प्रदर्शन के साथ कर सकते हैं।

डेटा को सॉर्ट करने के कई तरीक़े हैं। इस ट्यूटोरियल में, हम सबसे प्रभावी सॉर्टिंग तकनीकों में से एक का विश्लेषण करेंगे। “मर्ज सॉर्ट” एल्गोरिदम एक डिवाइड-एंड-कॉन्कर रणनीति का उपयोग करता है: यह पहले किसी असॉर्टेड एरे को छोटे-छोटे एरे में तोड़ता है, जिन्हें बाद में सही क्रम में मर्ज किया जाता है। 

आगे के अनुभागों में, हम मर्ज सॉर्ट एल्गोरिदम के सभी विवरणों, Python में इसकी रूप-रेखा, और सुचारू इम्प्लीमेंटेशन के लिए कुछ व्यवहारिक सुझावों पर चर्चा करेंगे।

Merge Sort क्या है?

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

यह एल्गोरिदम डिवाइड-एंड-कॉन्कर पैरेडाइम पर आधारित है, जिसे तीन भागों में बाँटा जा सकता है:

• Divide: यह चरण समस्या को छोटे उप-समस्याओं में विभाजित करता है। 
• Conquer: उप-समस्याओं को पुनरावृत्त (recursively) तरीक़े से हल किया जाता है। 
• Combine: उप-समस्याओं के समाधानों को मिलाकर अंतिम समाधान प्राप्त किया जाता है।

डिवाइड-एंड-कॉन्कर रणनीति

आइए देखें कि मर्ज सॉर्ट कैसे काम करता है। मान लीजिए कि हम निम्न संख्याओं को मर्ज सॉर्ट एल्गोरिदम लगाकर क्रम में लगाना चाहते हैं। एल्गोरिदम डेटा को पुनरावृत्त तरीके से दो भागों में बाँटता है और तब तक बाँटता जाता है जब तक प्रत्येक सूची में एक ही तत्व न रह जाए। फिर हम उन्हें दूसरे सूची में सॉर्ट करते हुए जोड़ते हैं।

मर्ज सॉर्ट समस्या। स्रोत: DataCamp

Merge Sort का समय और स्पेस जटिलता

यह पहले से जानना असंभव है कि किसी विशेष समस्या के लिए कौन सा सॉर्टिंग एल्गोरिदम सबसे अच्छा काम करेगा। एल्गोरिदम के अलावा कई चर (variables) पर विचार करना पड़ता है, जिनमें कोड लिखने के लिए इस्तेमाल की गई प्रोग्रामिंग भाषा, जिस हार्डवेयर पर उसे चलाया जा रहा है, और सॉर्ट किए जाने वाले डेटा की विशिष्टताएँ शामिल हैं। 

हालाँकि हम किसी सॉर्टिंग एल्गोरिदम के सटीक रनटाइम का पूर्वानुमान नहीं लगा सकते, फिर भी हम समय और स्पेस जटिलता का विश्लेषण करके विभिन्न सॉर्टिंग एल्गोरिदम के प्रदर्शन की तुलना कर सकते हैं।

मर्ज सॉर्ट की समय जटिलता

जैसा कि हमने Big O Notation और Time Complexity पर एक अलग गाइड में समझाया है, समय-जटिलता विश्लेषण का उद्देश्य किसी एल्गोरिदम के सटीक रनटाइम का अनुमान लगाना नहीं है, बल्कि यह आकलन करना है कि इनपुट डेटा की मात्रा बढ़ने पर उसके चलने के समय में कैसे परिवर्तन आता है।

समय-जटिलता विश्लेषण Big O नोटेशन में लिखा जाता है, जो किसी फ़ंक्शन के बढ़ने या घटने की दर का वर्णन करने वाला गणितीय नोटेशन है। मर्ज सॉर्ट की समय जटिलता लॉग-लीनियर या लीनरिथमिक होती है, जिसे O(N log(N)) के रूप में लिखा जाता है, जहाँ N सूची में तत्वों की संख्या है। अक्षर 'O' वृद्धि के 'order' को दर्शाता है। 

समय-जटिलता विश्लेषण में, लीनरिथमिक जटिलता का व्यवहार मोटे तौर पर रैखिक (linear) जटिलता जैसा होता है, यानी उसका निष्पादन डेटा की मात्रा के अनुपात में होगा। इसलिए, यदि डेटा दोगुना हो, तो एल्गोरिदम को डेटा प्रोसेस करने में लगने वाला समय भी दोगुना होना चाहिए, अर्थात विभाजनों और मर्ज की संख्या दोगुनी हो जाएगी।

क्योंकि मर्ज सॉर्ट की समय जटिलता लगभग रैखिक व्यवहार करती है, इसकी जटिलता सर्वश्रेष्ठ, औसत और सबसे खराब तीनों मामलों में समान रहती है। इसका मतलब है कि इनपुट क्रम जैसा भी हो, एल्गोरिदम को पूरा होने में हमेशा बराबर चरण लगेंगे।

मर्ज सॉर्ट की स्पेस जटिलता

अंततः, कार्य पूरा करने में लगने वाले समय के अलावा, एल्गोरिदम की जटिलता का विश्लेषण करते समय एक और महत्वपूर्ण पहलू यह आँकना है कि समस्या के बड़े होने पर एल्गोरिदम को कितना मेमोरी चाहिए होगी। 

इसे स्पेस जटिलता और सहायक स्पेस (auxiliary space) की अवधारणाएँ कवर करती हैं। सहायक स्पेस उस अतिरिक्त या अस्थायी स्पेस को संदर्भित करता है जिसका उपयोग एल्गोरिदम करता है, जबकि स्पेस जटिलता इनपुट आकार के सापेक्ष एल्गोरिदम द्वारा ली गई कुल स्पेस को दर्शाती है। दूसरे शब्दों में, स्पेस जटिलता में सहायक स्पेस और इनपुट द्वारा उपयोग की गई स्पेस, दोनों शामिल हैं।

मर्ज सॉर्ट की स्पेस जटिलता O(N) है। इसका कारण यह है कि यह इनपुट एरे के सॉर्टेड हिस्सों को मर्ज करने के लिए आकार N का एक सहायक एरे उपयोग करता है। सहायक एरे में मर्ज किया हुआ परिणाम रखा जाता है और इनपुट एरे को सॉर्टेड परिणाम से ओवरराइट कर दिया जाता है।

Python में Merge Sort का इम्प्लीमेंटेशन

आइए Python में मर्ज सॉर्ट एल्गोरिदम को लागू करें। इस एल्गोरिदम को कोड करने के कई तरीके हैं; हालाँकि, हम रिकर्शन-आधारित तरीके पर टिके रहेंगे, जो समझने में अपेक्षाकृत आसान है और इटरेशन-आधारित अन्य विकल्पों की तुलना में कम लाइनों का कोड मांगता है।

मर्ज सॉर्ट में रिकर्शन को समझना

यदि आप विषय में नए हैं, तो प्रोग्रामिंग में रिकर्शन तब होता है जब कोई फ़ंक्शन स्वयं को कॉल करता है। इन शक्तिशाली फ़ंक्शनों के बारे में सब कुछ जानने के लिए आप हमारा Understanding Recursive Functions in Python Tutorial देख सकते हैं।

मर्ज सॉर्ट को लागू करने के लिए, हम पहले बेस केस परिभाषित करते हैं: यदि सूची में केवल एक तत्व है, तो वह पहले से सॉर्टेड है, इसलिए हम तुरंत रिटर्न कर देते हैं। अन्यथा, हम सूची को दो हिस्सों left_half और right_half में बाँटते हैं और प्रत्येक पर merge_sort() को रिकर्सिव रूप से कॉल करते हैं। यह प्रक्रिया तब तक चलती है जब तक सभी उपसूचियों में एक-एक तत्व न रह जाए।

जब हमारे पास ये सॉर्टेड उपसूचियाँ होती हैं, तो हम मर्जिंग प्रक्रिया शुरू करते हैं। इसके लिए हम तीन इंडेक्स चर इनिशियलाइज़ करते हैं: i left_half में स्थिति ट्रैक करने के लिए, j right_half के लिए, और k अंतिम मर्ज की गई सूची के लिए। फिर हम दोनों हिस्सों के तत्वों की तुलना करते हैं। यदि left_half का मौजूदा तत्व छोटा है, तो हम उसे my_list[k] में रखते हैं और i को आगे बढ़ाते हैं। अन्यथा, हम right_half से तत्व लेते हैं, उसे my_list[k] में रखते हैं और j बढ़ाते हैं। हर तुलना के बाद, हम अंतिम सूची में अगले स्थान पर जाने के लिए k को आगे बढ़ाते हैं।

यह प्रक्रिया तब तक चलती है जब तक किसी एक हिस्से के सभी तत्वों की तुलना न हो जाए। यदि left_half या right_half में कोई तत्व शेष रह जाता है, तो हम उन्हें सीधे अंतिम सूची में जोड़ देते हैं, ताकि कोई डेटा छूट न जाए। चूँकि मर्ज सॉर्ट रिकर्सिव रूप से काम करता है, यह मर्जिंग प्रक्रिया रिकर्शन के हर स्तर पर चलती है, जब तक पूरी सूची सॉर्ट न हो जाए।

Python इम्प्लीमेंटेशन

नीचे आप पिछले डायग्राम की असॉर्टेड सूची का उपयोग करते हुए कोड पा सकते हैं:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]संचालित द्वारा

अन्य सॉर्टिंग एल्गोरिदम बनाम Merge Sort

मर्ज सॉर्ट एक काफ़ी तेज़ सॉर्टिंग एल्गोरिदम है, विशेष रूप से बड़े डेटाबेस के लिए उपयुक्त, और अक्सर अन्य एल्गोरिदम की तुलना के मानक के रूप में उपयोग किया जाता है। हालाँकि, छोटी सूचियों के मामले में इसका प्रदर्शन अन्य सॉर्टिंग एल्गोरिदम की तुलना में कम हो सकता है।

निम्न तालिका में, आप मर्ज सॉर्ट की तुलना अन्य लोकप्रिय सॉर्टिंग एल्गोरिदम से देख सकते हैं।

Merge Sort के व्यावहारिक उपयोग

मर्ज सॉर्ट बड़ी सूचियों को सॉर्ट करते समय उच्च प्रदर्शन देता है, लेकिन छोटी सूचियों पर इसकी कुशलता घट जाती है। इसी तरह, जब इनपुट सूचियों में पहले से कुछ हद तक क्रम मौजूद हो, तब भी यह कम कुशल होता है, क्योंकि सूची का क्रम चाहे जैसा हो, मर्ज सॉर्ट हमेशा वही चरण अपनाएगा।

एक बेहतरीन उपयोग-परिदृश्य जहाँ मर्ज सॉर्ट विशेष रूप से कारगर है, वह है लिंक्ड लिस्ट। लिंक्ड लिस्ट एक डेटा संरचना है जिसमें नोड्स का एक अनुक्रम होता है जो एक-दूसरे से रैखिक रूप से जुड़े होते हैं। प्रत्येक नोड में डेटा और अगले नोड से जोड़ने वाला लिंक होता है।

लिंक्ड लिस्ट के लिए मर्ज सॉर्ट को इसलिए प्राथमिकता दी जाती है क्योंकि इसे केवल डेटा तक अनुक्रमिक पहुँच की आवश्यकता होती है, जो लिंक्ड लिस्ट की प्रकृति के साथ अच्छी तरह मेल खाती है। साथ ही, मर्ज सॉर्ट एक स्थिर (stable) सॉर्टिंग एल्गोरिदम है (अर्थात यह सॉर्टेड आउटपुट में समान तत्वों के सापेक्ष क्रम को बनाए रखता है), जो लिंक्ड लिस्ट्स के क्रम को बनाए रखने में बहुत महत्वपूर्ण है।

सामान्य त्रुटियाँ और समस्या निवारण

मर्ज सॉर्ट एल्गोरिदम काफ़ी सीधा-सादा है, और कोड में सुधार की गुंजाइश सीमित है। फिर भी, आप इनपुट डेटा के आकार को ध्यान में रखकर अपनी सॉर्टिंग रणनीति की जटिलता बढ़ा सकते हैं। 

हम पहले ही स्थापित कर चुके हैं कि मर्ज सॉर्ट बड़े डेटासेट पर बेहतर काम करता है। छोटे डेटासेट के लिए, O(N^2) समय जटिलता वाले अन्य सॉर्टिंग एल्गोरिदम, जैसे इन्सर्शन सॉर्ट, बेहतर काम कर सकते हैं। इस स्थिति में, आपको बस एक साइज थ्रेशहोल्ड तय करना होगा, जिसके नीचे आप मर्ज सॉर्ट के बजाय इन्सर्शन सॉर्ट का उपयोग करें।

इसके अलावा, एक अच्छा विचार पैरेललाइज़ेशन की खोज करना होगा। पर्याप्त कंप्यूटिंग पावर के साथ मर्ज सॉर्ट के चरणों को आसानी से पैरेललाइज़ किया जा सकता है, जिससे पूरा करने में लगने वाला समय घट जाता है। पैरेलल कंप्यूटिंग के बारे में अधिक जानने के लिए हमारा CPU बनाम GPU गाइड पढ़ें। 

निष्कर्ष

मर्ज सॉर्ट सबसे प्रभावी और लोकप्रिय सॉर्टिंग एल्गोरिदम में से एक है, लेकिन एल्गोरिदम के अद्भुत और निरंतर विस्तार करते ब्रह्मांड में सीखने के लिए बहुत कुछ है। यदि आप एल्गोरिदम की तकनीकी बारीकियों, उनके काम करने के तरीक़ों और उनसे जुड़ी जटिलता, गुण और सीमाओं में रुचि रखते हैं, तो ये DataCamp संसाधन आपकी सीख जारी रखने में मदद कर सकते हैं:

• Introduction to Data Structures and Algorithms Course 
• Python Programming Skill Track
• Python Data Fundamentals Skill Track
• Intermediate Python Course
• Data Analyst in Python Career Track 
• Big O Notation and Time Complexity