रूबी में इंसर्शन सॉर्ट को समझना

नोट:रूबी के साथ विभिन्न सॉर्टिंग एल्गोरिदम को लागू करने पर विचार करने वाली श्रृंखला में यह भाग 4 है। भाग 1 ने बबल सॉर्ट की खोज की, भाग 2 ने चयन प्रकार की खोज की, और भाग 3 ने मर्ज सॉर्ट की खोज की।

जैसा कि हम डेटा सॉर्ट करने के लिए विभिन्न तरीकों का पता लगाना जारी रखते हैं, हम इंसर्शन सॉर्ट की ओर रुख करते हैं। सम्मिलन प्रकार पसंद करने के कई कारण हैं! सबसे पहले, सम्मिलन क्रम स्थिर है , जिसका अर्थ है कि यह समान कुंजियों वाले तत्वों के सापेक्ष क्रम को नहीं बदलता है। यह एक इन-प्लेस एल्गोरिथम भी है , जिसका अर्थ है कि यह सॉर्ट किए गए तत्वों को संग्रहीत करने के लिए एक नई सरणी नहीं बनाता है। अंत में, सम्मिलन क्रम लागू करने के लिए एक बहुत ही सरल एल्गोरिथम है, जैसा कि आप जल्द ही देखेंगे!

क्यों केयर करें

यहां टूटे हुए रिकॉर्ड की तरह लगने से बचना मुश्किल है, लेकिन जैसा कि हमने पिछली सभी पोस्टों में चर्चा की है, डेटा को सॉर्ट करने के लिए विभिन्न तंत्रों की समझ होना महत्वपूर्ण है और विभिन्न तरीकों में से प्रत्येक के साथ ट्रेड-ऑफ क्या हैं। उदाहरण के लिए, जबकि सम्मिलन क्रम बड़े डेटासेट के लिए बहुत उपयोगी नहीं है (हम इसे नीचे और अधिक खोजेंगे), यह छोटे डेटासेट और पहले से ही सॉर्ट किए जाने के करीब के लिए ठीक और काफी कुशल हो सकता है। एक बार जब हम कार्यान्वयन के माध्यम से चलते हैं तो आप सीखेंगे कि क्यों। निश्चित रूप से, आप अक्सर अंतर्निहित विधियों का उपयोग करेंगे जो आपकी पसंद की प्रोग्रामिंग भाषा सॉर्टिंग के लिए प्रदान करती है, लेकिन यह एक साक्षात्कार प्रश्न के रूप में या तो जोड़ी-कार्यक्रम अभ्यास या शायद समय जटिलता से संबंधित हो सकती है। सौभाग्य से, जब तक हम इस पोस्ट को पूरा नहीं कर लेते, तब तक आप इंसर्शन सॉर्ट को कोड करने और समय की जटिलता को आसानी से समझने में सक्षम होंगे।

एक दृश्य प्रतिनिधित्व

इससे पहले कि हम कोडिंग शुरू करें, मैं निम्नलिखित वीडियो को देखने की अत्यधिक अनुशंसा करता हूं। यह एक नृत्य का उपयोग करते हुए सम्मिलन प्रकार की व्याख्या करता है, और व्यक्तिगत रूप से, मैं इसे पर्याप्त रूप से प्राप्त नहीं कर सकता! :)

कोड का चरण-दर-चरण वॉक-थ्रू

आइए कोड देखें!

def insertion_sort(array)
    for i in 1...(array.length)  # Step 1
        j = i # Step 2
        while j > 0 # Step 3
            if array[j-1] > array[j] # Step 4
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
            else
                break
            end
            j = j - 1 # Step 5
        end
    end
    return array
end

चरण 1:

हम for . से शुरू करते हैं लूप जो वैरिएबल i . सेट करता है 1 तक और i . तक वृद्धि जारी रखता है हमारे सरणी की लंबाई के बराबर है।

चरण 2:

हम एक और वैरिएबल बनाते हैं j और इसे 1 के मान से प्रारंभ करें (क्योंकि i . यही है है)।

चरण 3:

इसके बाद, हमारे पास एक नेस्टेड while है लूप जो j . तक जारी रहेगा शून्य से बड़ा है। चूंकि हम j . से शुरू करते हैं 1 के बराबर, हम जानते हैं कि यह कम से कम एक बार निष्पादित होगा।

चरण 4:

if... else ब्लॉक शायद पहली बार में डरावना लग रहा है, लेकिन चिंता न करें। एक बार जब हम इसके माध्यम से चलते हैं तो यह समझ में आता है (और आप हमेशा नृत्य YouTube उदाहरण पर फिर से जा सकते हैं!)।

if . के लिए हालत, हम जाँचते हैं कि क्या [j-1] array[j] . से बड़ा है . चूंकि j वर्तमान में 1 है, हम अनिवार्य रूप से array[0] . की तुलना करेंगे array[1] . के साथ . यह समझ में आता है क्योंकि हम सरणी के पहले दो तत्वों की तुलना कर रहे हैं।

यदि पहला तत्व (array[0] ) अगले वाले से बड़ा है (array[1] ), तो निश्चित रूप से हमें स्वैप करने की आवश्यकता है, जो कि if . के भीतर होता है खंड मैथा। हालांकि, अगर array[0] . में मान array[1] . में मान से कम है , फिर बढ़िया! हमें कुछ भी करने की आवश्यकता नहीं है क्योंकि यह पहले से ही क्रमबद्ध है, इसलिए हम बस break दबाते हैं else में ब्लॉक करें।

चरण 5:

यहां से, हम j . घटाते हैं . अब, हम for . पर वापस आ गए हैं लूप, और i अब 2 होने जा रहा है . आप कल्पना कर सकते हैं कि हम array[1] . की तुलना कैसे करेंगे? array[2] . के साथ while . के भीतर पहली पुनरावृत्ति के लिए लूप, और फिर हम वास्तव में while . से गुजरेंगे फिर से लूप करें क्योंकि हमारा j 2 . पर शुरू हुआ बनाम 1 ।

वास्तविक डेटा के साथ उदाहरण

आइए निम्नलिखित उदाहरण सरणी का उपयोग करके इस कोड के माध्यम से चलते हैं:[5,7,2,10,9,12]

पहले पुनरावृत्ति में, हम 5 . की तुलना करेंगे और 7 . चूंकि 5 < 7 , हम जल्दी से if/else . से बाहर निकल जाते हैं और आगे बढ़ें।

अगले पुनरावृत्ति में, हम 7 . की तुलना करते हैं और 2 . अब, इन मानों की अदला-बदली करनी होगी, इसलिए हमारे पास [5, 2, 7, 10, 9, 12] होगा। . फिर, हम 2 . की अदला-बदली करेंगे फिर से 5 . के साथ [2, 5, 7, 10, 9, 12] . के साथ समाप्त करने के लिए ।

अगले पुनरावृत्ति में for . के भीतर लूप, हम तुलना करेंगे 10 और 7 -- वाह! वे पहले से ही क्रम में हैं।

आगे बढ़ते हुए, हम 10 . की तुलना करते हैं और 9 और पाते हैं कि हमें स्वैप करने की आवश्यकता है। फिर, 7 9 . से कम है , इसलिए हमें कोई अन्य स्वैप नहीं करना होगा। अब हमारे पास [2, 5, 7, 9, 10, 12] . बचा है ।

अंतिम पुनरावृत्ति 12 . ढूँढता है , जो 10 . से बड़ा है , तो वोइला! हम कर चुके हैं और क्रमबद्ध हैं।

प्रदर्शन विश्लेषण

जबकि कुछ सॉर्टिंग एल्गोरिदम जिन्हें हमने देखा है, अर्थात् बबल सॉर्ट, वास्तविक जीवन में बहुत कम अभ्यास किया जाता है, सम्मिलन सॉर्ट एक उचित समाधान हो सकता है। कल्पना कीजिए कि अगर हमारी सरणी पहले से ही क्रमबद्ध थी - सम्मिलन क्रम बहुत जल्दी और कुशलता से चलेगा। दूसरी तरफ, क्या होता है यदि हमें एक सरणी को उल्टे क्रम में क्रमबद्ध करने की आवश्यकता होती है। प्रविष्टि क्रम के लिए यह एक दुःस्वप्न की स्थिति होगी।

यदि ऐरे पहले से ही सॉर्ट किया गया है, तो इंसर्शन सॉर्ट कोड O(n) . पर चलेगा चूंकि इसे केवल n . के माध्यम से लूप करना होगा बार। यदि आप इसे सहन करना चाहते हैं, तो एक puts i add जोड़ें विधि के शीर्ष पर और पहले से क्रमबद्ध सरणी में गुजरने वाले प्रोग्राम को चलाएं।

यदि ऐरे को रिवर्स-सॉर्ट किया गया है, तो इंसर्शन सॉर्ट कोड O(n^2) पर चलेगा। आप इसे अपने दिमाग में कल्पना करने में सक्षम हो सकते हैं। चूंकि इसे लगातार स्वैप करना होगा, यह if . पर हिट करेगा हर एक तत्व के लिए शर्त। ओह! फिर से, बेझिझक इसे एक रिवर्स-सॉर्टेड एरे में पास करके आज़माएँ और एक काउंटर वेरिएबल बनाएं जो प्रिंट आउट हो।

हालांकि सबसे खराब स्थिति है O(n^2) जैसा कि आपको याद होगा, बबल सॉर्ट और चयन सॉर्ट के लिए समान है, सम्मिलन सॉर्ट आमतौर पर बेहतर होता है। ऐसा इसलिए है, क्योंकि जैसा कि हमने देखा, सबसे अच्छा मामला हो सकता है O(n) , जबकि चयन प्रकार के लिए सबसे अच्छा मामला है O(n^2) . इंसर्शन सॉर्ट में बबल सॉर्ट की तुलना में कम स्वैप होते हैं, इसलिए यह इस लड़ाई को जीतता है।

रैप अप

मुझे उम्मीद है कि यह पोस्ट मददगार रही है और आप सम्मिलन प्रकार के पेशेवरों और विपक्षों को समझने के साथ-साथ एल्गोरिदम कैसे काम करते हैं, इसके बारे में आश्वस्त महसूस करते हैं। यदि आप अभी भी अधिक के लिए खुजली कर रहे हैं, तो मेरा सुझाव है कि सम्मिलन क्रम के लिए विकिपीडिया पृष्ठ देखें।