मर्ज सॉर्ट
मर्ज सॉर्ट सबसे तेज़ सॉर्टिंग एल्गोरिदमों में से एक है। कई एप्लिकेशन उत्पादन (प्रोडक्शन) में मर्ज सॉर्ट के किसी न किसी संस्करण का उपयोग करती हैं। हम पहले ऐसे एल्गोरिदम देख चुके हैं जो समय में चलते हैं, जैसे कि Bubble sort या Selection sort। मर्ज सॉर्ट इन सभी वर्गीय (क्वाड्रेटिक) सॉर्टिंग एल्गोरिदमों की तुलना में कहीं तेज़ है और समय में चलता है।
मर्ज सॉर्ट एक डिवाइड-एंड-क conquer एल्गोरिदम है, जो दिए गए ऐरे के भागों को रेकर्सिव तरीके से सॉर्ट करता है और फिर उन्हें मर्ज करता है। इस एल्गोरिदम का मूल हिस्सा दो सॉर्ट किए गए ऐरे को मिलाकर एक नया सॉर्ट किया हुआ ऐरे बनाने की क्षमता है। एल्गोरिदम काम करते समय ऐरे को दो भागों में विभाजित करता है। फिर पहले भाग को पुनरावृत्त तरीके से (रेकर्सिव्ली) सॉर्ट करता है। उसके बाद दूसरे भाग को भी रेकर्सिव्ली सॉर्ट करता है। आखिर में दोनों सॉर्ट किए हुए ऐरे को मिलाकर एक नया सॉर्ट किया हुआ ऐरे तैयार करता है:
def merge(a, b):
i, j, res = 0, 0, [] # a और b के लिए इंडेक्स, तथा परिणाम ऐरे
while i < len(a) or j < len(b): # जब तक कोई तत्व बचा हुआ है
ai = a[i] if i < len(a) else float('inf')
bj = b[j] if j < len(b) else float('inf')
if ai < bj: # अगर a[i] < b[j] => a[i] को लें
res.append(ai) # परिणाम में a[i] जोड़ें
i += 1 # अगला तत्व लें
else: # अगर a[i] >= b[j] => b[j] को लें
res.append(bj) # परिणाम में b[j] जोड़ें
j += 1 # अगला तत्व लें
return res
def merge_sort(a):
if len(a) <= 1: # सॉर्ट करने के लिए कुछ नहीं है
return a # मूल ऐरे वापस कर दें
l = merge_sort(a[: len(a) // 2]) # बाएँ भाग को सॉर्ट करें
r = merge_sort(a[len(a) // 2:]) # दाएँ भाग को सॉर्ट करें
return merge(l, r)प्रत्येक चरण पर, एल्गोरिदम ऐरे को लेता है, उसे दो भागों में बाँटता है, उन दोनों को अलग-अलग सॉर्ट करता है, और फिर दोनों परिणामी ऐरे को मिलाकर एक नया ऐरे बनाता है। ध्यान दें कि पहले जिन एल्गोरिदमों पर हमने चर्चा की थी, वे प्रारंभिक ऐरे को इन्हीं स्थानों (इन-प्लेस) पर संशोधित करते थे, जबकि मर्ज सॉर्ट एल्गोरिदम प्रत्येक पुनरावृत्ति में एक नया ऐरे बनाता है। मर्ज सॉर्ट को इन-प्लेस कार्यान्वित करना काफ़ी चुनौतीपूर्ण है। क्या आप बता सकते हैं ऐसा क्यों है?
आइए कुछ ऐरे पर एल्गोरिदम का सिम्युलेशन करें:
[4, 1, -1, 0, 2, 8]
merge_sort([4, 1, -1, 0, 2, 8]):merge_sort([4, 1, -1])merge_sort([0, 2, 8])
merge_sort([4, 1, -1])merge_sort([4])→ return[4]merge_sort([1, -1])
merge_sort([0, 2, 8])merge_sort([1])→ return[1]merge_sort([-1])→ return[-1]
merge_sort([4, 1, -1]):
merge_sort([4])→ return[4]
merge_sort([1, -1])merge_sort([0])→ return[0]merge_sort([2, 8])
merge_sort([1, -1]):merge_sort([2])→ return[2]merge_sort([8])→ return[8]
merge_sort([1])→ return[1]
merge_sort([-1])→ return[-1]
- Back to
merge_sort([1, -1])→ return[-1, 1]
चुनौती
आपको दिए गए
n पूर्णांकों के ऐरे को मर्ज सॉर्ट एल्गोरिदम का उपयोग करके अवरोही क्रम (descending order) में सॉर्ट करना है।इनपुट
इनपुट की पहली पंक्ति में एक पूरा संख्या
n (1 ≤ n ≤ 100 000) दी गई है।अगली पंक्ति में
n रिक्त-चिन्हों से अलग किए गए पूर्णांक ( ≤ ≤ ) हैं, जो प्रारंभिक ऐरे को दर्शाते हैं।आउटपुट
प्रोग्राम को
n पूर्णांकों को अवरोही क्रम में (space के साथ अलग किए हुए) प्रिंट करना चाहिए।उदाहरण
Input | Output |
4
7 4 9 1 | 9 7 4 1 |
5
-4 8 2 -3 6 | 8 6 2 -3 -4 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 10 MB