Python एल्गोरिदम

Python में Merge Sort

Divide-and-conquer से data sort करें।

  • मध्यम
  • 2 मिनट में पढ़ें
  • 1 चलाने योग्य उदाहरण

में Merge Sort क्या है?

समस्या क्या है

आसान sorts लिस्ट बड़ी होने पर बहुत धीमे हो जाते हैं: डेटा दोगुना करने पर काम चार गुना हो जाता है। Merge sort समस्या को छोटी-छोटी आसान समस्याओं में बाँटता है, और काम को डेटा से बस थोड़ा तेज़ी से बढ़ने देता है।

ऐसे समझें

Merge sort ऐसा है जैसे दोस्तों के साथ परीक्षा की कॉपियों का बड़ा ढेर sort करना। आप ढेर को आधा करते हैं, हर आधा किसी को दे देते हैं, और वे भी अपना ढेर आधा करते हैं, जब तक हर किसी के पास एक कॉपी न रह जाए। फिर दो-दो लोग अपने sorted ढेर मिलाते हैं, हमेशा ऊपर वाली छोटी कॉपी लेकर, जब तक एक sorted ढेर न बचे।

परीक्षा की कॉपियों से कोड तक
if len(values) <= 1:📄 एक कॉपी पहले से sorted है
merge_sort(values[:middle])✂️ ढेर बाँटिए और हर आधा sort कीजिए
left[left_index] <= right[right_index]🤝 मिलाइए: ऊपर वाली छोटी कॉपी लीजिए
result + left[left_index:] + right[right_index:]📚 दूसरे ढेर में जो बचा है वह जोड़िए
अकेले आइटम तक बाँटिए, फिर sorted ढेर वापस मिलाइए।
एक वाक्य में

Merge sort लिस्ट को आधा करता है, हर आधे को recursion से sort करता है और दोनों sorted आधों को मिला देता है। इसमें O(n log n) समय लगता है।

मुख्य बातें

  1. if len(values) <= 1: return values base case है जो recursion रोकता है।
  2. merge_sort(values[:middle]) और merge_sort(values[middle:]) दोनों आधे sort करते हैं।
  3. while लूप left या right से आगे वाली छोटी वैल्यू लेता है, जब तक एक लिस्ट ख़त्म न हो जाए।
  4. left[left_index:] और right[right_index:] बची हुई वैल्यू जोड़ते हैं, जो पहले से sorted हैं।
  5. बराबर वैल्यू होने पर <= पहले बाईं तरफ़ से लेता है, जिससे बराबर वैल्यू अपने मूल क्रम में रहती हैं।

इसका उपयोग कब करें?

  • बड़े डेटा को भरोसेमंद तरीके से तेज़ी से sort करना, बिना किसी बुरे worst case के।
  • Linked list या मेमोरी से बड़े डेटा को sort करना (external sorting)।
  • Divide and conquer सीखना, जो कई एल्गोरिदम में इस्तेमाल होने वाला पैटर्न है।

कब ज़रूरत नहीं

  • सामान्य Python कोड: sorted() पहले से Timsort इस्तेमाल करता है, जो merge sort और insertion sort का अच्छी तरह tune किया हुआ मेल है।
  • बहुत कम मेमोरी: merge sort को मिली हुई लिस्ट के लिए अतिरिक्त जगह चाहिए।

Python में Merge Sort Visualizer

O(n log n)

हर comparison और data movement देखने के लिए चलाएँ या अगला चरण दबाएँ।

उदाहरण कोड

कोड चलाएँ →
main.py
def merge_sort(values):
    if len(values) <= 1:
        return values
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    result = []
    left_index = right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    return result + left[left_index:] + right[right_index:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
इस उदाहरण के लिए Run बटन बनाएँ

अपेक्षित आउटपुट

[3, 9, 10, 27, 38, 43, 82]

यह कैसे काम करता है

यह O(n log n) समय सुनिश्चित करता है और O(n) अतिरिक्त memory उपयोग करता है।

मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।

अभ्यास के कार्य

बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।

  1. खाली input, एक element और duplicate values जाँचें।
  2. हर चरण के बाद state दिखाएँ।
  3. Performance को दूसरे solution से तुलना करें।
Python IDE में चलाएँ →

आम गलतियाँ

बचे हुए आइटम भूल जाना

जब एक आधा ख़त्म हो जाता है, तो दूसरे आधे का बाकी हिस्सा छूट जाता है।

समस्या
return result
सुधार
return result + left[left_index:] + right[right_index:]

यह पाठ पूरा कर लिया?

अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।

अगला: Memoization के साथ Recursive Fibonacci →

चैलेंज से अभ्यास करें

इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।

सभी चैलेंज