Insertion sort: तास मिलाएजस्तै
Insertion sort ले हरेक सङ्ख्या पालैपालो लिएर बायाँका मिलिसकेका सङ्ख्यामाझ यसको ठाउँमा कसरी सार्छ, हातमा तास मिलाएजस्तै, हेर्नुहोस्। यसका तुलना र swap गन्नुहोस्, र मिसिएको, मिलेको र उल्टो सूचीमा यसलाई bubble sort र selection sort सँग दाँज्नुहोस्।
मूल अवधारणा
Insertion sort ले बायाँ मिलेको भाग राख्छ र अर्को सङ्ख्यालाई हरेक ठूलो सङ्ख्या नाघ्दै सारेर त्यसभित्र राख्छ; लगभग मिलेको सूचीमा यसले धेरै कम काम गर्छ
पाठ: Algorithm
हातमा तास कसरी मिलाउनुहुन्छ, सोच्नुहोस्। बायाँका तास क्रममा राख्नुहुन्छ, अर्को तास टिप्नुहुन्छ, र अटाउने ठाउँ नआएसम्म त्यसलाई हरेक ठूलो तासभन्दा बायाँ सार्नुहुन्छ। Insertion sort ले सङ्ख्यासँग यस्तै गर्छ। पहिलो सङ्ख्या एक्लै पहिले नै मिलेको हुन्छ। अनि यसले दोस्रो सङ्ख्या, key, लिन्छ र यसको बायाँका सङ्ख्यासँग तुलना गर्छ: बायाँको सङ्ख्या ठूलो भएसम्म तिनले ठाउँ साट्छन्। बायाँको सङ्ख्या सानो भएपछि, वा बायाँ केही नरहेपछि, key आफ्नो ठाउँमा पुग्छ, र मिलेको भाग एकले बढ्छ। पहिले नै मिलेको सूचीमा हरेक key लाई एउटा तुलना मात्र चाहिन्छ र कुनै swap चाहिँदैन, त्यसैले लगभग क्रममा भएको सूचीका लागि insertion sort धेरै छिटो हुन्छ।
के सिक्नुहुनेछ
- Insertion sort ले हरेक सङ्ख्यालाई बायाँको मिलेको भागमा कसरी राख्छ, वर्णन गर्नुहोस्।
- Key ठूला सङ्ख्या नाघ्दै बायाँ सर्दा trace गर्नुहोस्।
- Insertion sort ले गर्ने तुलना र swap गन्नुहोस्।
- एउटै सूचीमा insertion sort लाई bubble sort र selection sort सँग दाँज्नुहोस्।
सुरु गर्नुअघि
- Bubble sort र selection sort ले सूची कसरी मिलाउँछन्, थाहा हुनुपर्छ।
सामग्री
- केही तास, वा सङ्ख्या लेखिएका कागजका टुक्रा
उपकरण
- केही पनि चाहिँदैन
विधि
- मिसिएको सूचीमा insertion sort चलाएर तुलना र swap पढ्नुहोस्।
- Step गर्दै हरेक key बायाँ सरेको हेर्नुहोस्।
- मिलेको र उल्टो सूची मिलाएर काम अरू sort सँग दाँज्नुहोस्।
- अभ्यासका challenge हरूको उत्तर दिनुहोस्।