Merge sort: टुक्राऊ अनि जिताऊ
आठवटा सङ्ख्याको सूचीलाई हरेक भागमा एउटा मात्र सङ्ख्या नबचेसम्म बारम्बार आधा गर्नुहोस्, अनि सधैँ अगाडिको सानो सङ्ख्या लिँदै भागहरू फेरि जोड्नुहोस्। तुलना गन्नुहोस्, र मिसिएको, मिलेको र उल्टो सूचीमा bubble sort र insertion sort सँग दाँज्नुहोस्।
मूल अवधारणा
Merge sort ले हरेक भागमा एउटा सङ्ख्या नबचेसम्म सूचीलाई आधा गर्छ, अनि सधैँ अगाडिको सानो सङ्ख्या लिँदै मिलेका भाग जोड्छ; यसको तुलना n log n जस्तो बढ्छ, bubble sort को n² भन्दा धेरै ढिलो
पाठ: Algorithm
Merge sort ले divide and conquer भन्ने तरिका प्रयोग गर्छ: ठूलो समस्यालाई सजिलै हल हुने साना समस्यामा टुक्र्याइन्छ, अनि तिनका उत्तर जोडिन्छन्। एउटा मात्र सङ्ख्या भएको सूची पहिले नै मिलेको हुन्छ, त्यसैले merge sort ले हरेक भागमा एउटा मात्र सङ्ख्या नबचेसम्म सूचीलाई आधा गरिरहन्छ। त्यसपछि भागहरूलाई जोडी-जोडी गरेर फेरि जोड्छ। मिलेका दुई भाग जोड्न यसले दुवैको अगाडिको सङ्ख्या मात्र हेर्छ र सानोलाई लिन्छ, दुवै भाग नसकिएसम्म यसै गरिरहन्छ। हरेक जोडाइमा भागहरू एक पटक मात्र हेरिन्छन्, र सूचीलाई थोरै पटक मात्र आधा गर्न सकिन्छ (8 बाट 4, 2 र 1, तीन पटकमा), त्यसैले merge sort ले करिब n × log₂ n तुलना गर्छ। Bubble sort र insertion sort लाई n × (n − 1) ÷ 2 तुलना लाग्न सक्छ, जुन सूची लामो हुँदै जाँदा धेरै छिटो बढ्छ।
के सिक्नुहुनेछ
- Merge sort ले सूचीलाई एक्ला सङ्ख्यासम्म कसरी टुक्र्याउँछ, व्याख्या गर्नुहोस्।
- हरेक पटक अगाडिको सानो सङ्ख्या लिँदै मिलेका दुई सूची जोड्नुहोस्।
- उही सूचीमा merge sort, bubble sort र insertion sort का तुलना दाँज्नुहोस्।
- लामो सूचीमा merge sort किन छिटो छ, व्याख्या गर्नुहोस्।
सुरु गर्नुअघि
- Bubble sort वा insertion sort, र तुलना भनेको के हो, थाहा हुनुपर्छ।
सामग्री
- हातैले टुक्र्याउन र जोड्न अङ्क लेखिएका आठवटा card
उपकरण
- केही पनि चाहिँदैन
विधि
- मिसिएको सूचीमा merge sort चलाएर यसका तुलना गन्नुहोस्।
- उही सूचीमा bubble sort चलाएर दाँज्नुहोस्।
- उल्टो सूचीलाई दुवै तरिकाले मिलाउनुहोस्।
- अभ्यासका challenge हरूको उत्तर दिनुहोस्।