सामान्य विचार
बाँटो और जीतो (रोमानियाई में Divide et Impera, लैटिन में "बाँटो और राज करो") के तीन भाग हैं:
- समस्या को उसी तरह की छोटी समस्याओं में बाँटो (divide)।
- हल करो (conquer): हर छोटी समस्या हल करो। बहुत छोटी हो (आधार स्थिति, base case) तो सीधे हल करो, वरना वही तरकीब फिर लगाओ (रिकर्शन)।
- छोटे उत्तरों को जोड़कर बड़ी समस्या का उत्तर बनाओ (combine)।
यह तब चलता है जब छोटी समस्याएँ एक-दूसरे पर निर्भर न हों और जोड़ना सस्ता हो। फ़ंक्शन खुद को कैसे बुलाता है, यह रिकर्शन में देखें।
मर्ज सॉर्ट: सबसे मशहूर उदाहरण
n संख्याओं की सूची सजाओ:
mergeSort(list): if list has 1 item: return list left = mergeSort(first half) right = mergeSort(second half) return merge(left, right)
दो क्रमबद्ध सूचियों को मिलाना (merge): दोनों के पहले तत्व देखो, छोटा वाला निकालो, और तब तक दोहराओ जब तक दोनों खाली न हों। n तत्व मिलाने में लगभग n कदम लगते हैं।
बँटवारे के लगभग log₂ n स्तर होते हैं (8 तत्व: 3 स्तर) और हर स्तर पर लगभग n काम होता है, इसलिए कुल लगभग n log₂ n कदम। यह सरल तरीके (बबल सॉर्ट, लगभग n² कदम) से बहुत तेज़ है।
बाइनरी सर्च: आधा करते जाओ
क्रमबद्ध सूची में संख्या खोजनी हो तो उसे बीच के तत्व से मिलाओ। छोटी हो तो केवल बायाँ आधा देखो; बड़ी हो तो केवल दायाँ। हर जाँच में आधे तत्व छूट जाते हैं।
n तत्वों के लिए अधिकतम लगभग log₂ n जाँचें चाहिए: 16 के लिए 4, 1000 के लिए 10 और 10 लाख के लिए केवल 20।
अन्य उपयोग
- क्विकसॉर्ट: एक पिवट चुनो, छोटे तत्व बाएँ और बड़े दाएँ रखो, फिर दोनों ओर सजाओ।
- तेज़ घात: a⁸ = ((a²)²)²। 7 की जगह केवल 3 गुणा। सम n के लिए aⁿ = (aⁿ/²)²।
- सूची का अधिकतम: हर आधे का अधिकतम निकालो, फिर बड़ा चुनो।
- हनोई की मीनार, बड़ी संख्याओं का तेज़ गुणा, सबसे पास के दो बिंदु भी इसी से हल होते हैं।
कब काम नहीं आता
यदि छोटी समस्याएँ एक-दूसरे से मिलती हैं (वही उप-समस्या बार-बार आती है, जैसे फ़िबोनाची में) तो साधारण बाँटो-और-जीतो काम दोहराता है। तब डायनेमिक प्रोग्रामिंग लो। कई विकल्प आज़माकर वापस लौटना हो तो बैकट्रैकिंग लो।
करके देखो
8 ताश के पत्ते लो। उन्हें 4-4 के दो ढेरों में, फिर 2-2 में, फिर अकेले पत्तों में बाँटो। फिर जोड़ियाँ मिलाते जाओ, हमेशा ऊपर का छोटा पत्ता लेकर। गिनो कितने स्तर बने। 3D में स्लाइडर चलाने से पहले अगली अवस्था का अंदाज़ा लगाओ।
मुख्य सूत्र और परिभाषाएँ
- n तत्वों के लिए आधा करने के स्तर = log₂ n (8 → 3, 16 → 4, 1024 → 10)
- मर्ज सॉर्ट का समय ≈ n × log₂ n
- बाइनरी सर्च की जाँचें ≤ ⌊log₂ n⌋ + 1
- तेज़ घात: aⁿ = (aⁿ/²)² (n सम), aⁿ = a × (a⁽ⁿ⁻¹⁾/²)² (n विषम)
हल किए गए उदाहरण
1. 8 तत्वों को अकेले तत्वों तक बाँटो। बँटवारे के कितने स्तर?
8 → 4 → 2 → 1। यानी 3 स्तर (log₂ 8 = 3)।
2. क्रमबद्ध सूचियाँ [2, 5, 9] और [3, 4, 10] मिलाओ।
हर बार आगे का छोटा लो: 2, 3, 4, 5, 9, 10। परिणाम: [2, 3, 4, 5, 9, 10]।
3. [5, 2, 7, 1] को मर्ज सॉर्ट से सजाओ। चरण दिखाओ।
बाँटो: [5, 2] और [7, 1]। फिर बाँटो: [5] [2] [7] [1]। जोड़ियाँ मिलाओ: [2, 5] और [1, 7]। मिलाओ: [1, 2, 5, 7]।
4. 1000 क्रमबद्ध संख्याओं के लिए बाइनरी सर्च में अधिकतम कितनी जाँचें?
2¹⁰ = 1024 ≥ 1000, इसलिए अधिकतम 10 जाँचें।
5. तेज़ घात से 2¹⁰ निकालो। कितने गुणा लगे?
2¹⁰ = (2⁵)²। 2⁵ = 2 × (2²)²। 2² में 1 गुणा, (2²)² में 1 और, ×2 में 1 और, अंतिम वर्ग में 1 और: 9 की जगह 4 गुणा।
6. [3, 8, 15, 23, 31, 42, 57] में 23 खोजो। बाइनरी सर्च दिखाओ।
बीच का तत्व 23 है (7 में से चौथा)। 1 जाँच में मिल गया।
आम गलतियाँ
- आधार स्थिति भूल जाना, जिससे बाँटना कभी नहीं रुकता।
- बिना क्रमबद्ध सूची पर बाइनरी सर्च लगाना। सूची क्रमबद्ध होनी चाहिए।
- सोचना कि मर्ज सॉर्ट बाँटते समय सजाता है। सजाना मिलाते समय होता है।
- ओवरलैप होती उप-समस्याओं पर बाँटो-और-जीतो लगाना, जिससे काम दोहराता है।