में 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:]📚 दूसरे ढेर में जो बचा है वह जोड़िएMerge sort लिस्ट को आधा करता है, हर आधे को recursion से sort करता है और दोनों sorted आधों को मिला देता है। इसमें O(n log n) समय लगता है।
मुख्य बातें
if len(values) <= 1: return valuesbase case है जो recursion रोकता है।merge_sort(values[:middle])औरmerge_sort(values[middle:])दोनों आधे sort करते हैं।whileलूपleftयाrightसे आगे वाली छोटी वैल्यू लेता है, जब तक एक लिस्ट ख़त्म न हो जाए।left[left_index:]औरright[right_index:]बची हुई वैल्यू जोड़ते हैं, जो पहले से sorted हैं।- बराबर वैल्यू होने पर
<=पहले बाईं तरफ़ से लेता है, जिससे बराबर वैल्यू अपने मूल क्रम में रहती हैं।
इसका उपयोग कब करें?
- बड़े डेटा को भरोसेमंद तरीके से तेज़ी से 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 देखने के लिए चलाएँ या अगला चरण दबाएँ।
उदाहरण कोड
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]))
अपेक्षित आउटपुट
[3, 9, 10, 27, 38, 43, 82]
यह कैसे काम करता है
यह O(n log n) समय सुनिश्चित करता है और O(n) अतिरिक्त memory उपयोग करता है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।
आम गलतियाँ
बचे हुए आइटम भूल जाना
जब एक आधा ख़त्म हो जाता है, तो दूसरे आधे का बाकी हिस्सा छूट जाता है।
return result
return result + left[left_index:] + right[right_index:]
यह पाठ पूरा कर लिया?
अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।
चैलेंज से अभ्यास करें
इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।
सभी चैलेंज