नोट: यह रूबी के साथ विभिन्न सॉर्टिंग एल्गोरिदम को लागू करने पर एक श्रृंखला का भाग 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] में मान से कम है, तो बढ़िया! हमें कुछ भी करने की आवश्यकता नहीं है क्योंकि यह पहले से ही सॉर्टेड है, इसलिए हम बस else ब्लॉक में break हिट करते हैं।
चरण 5:
यहां से, हम j को डिक्रीमेंट करते हैं। अब, हम for लूप पर वापस आ गए हैं, और i अब 2 होने जा रहा है। आप कल्पना कर सकते हैं कि हम while लूप के भीतर पहली इटरेशन के लिए array[1] की तुलना array[2] से करेंगे, और फिर हम वास्तव में while लूप से फिर से गुजरेंगे क्योंकि हमारा j 1 बनाम 2 पर शुरू हुआ था।
वास्तविक डेटा के साथ उदाहरण
आइए निम्नलिखित उदाहरण सरणी का उपयोग करके इस कोड के माध्यम से चलते हैं: [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 जोड़ें और प्रोग्राम को पहले से सॉर्टेड सरणी पास करके चलाएं।
यदि सरणी रिवर्स-सॉर्टेड है, तो इंसर्शन सॉर्ट कोड O(n^2) पर चलेगा। आप इसे अपने दिमाग में कल्पना करने में सक्षम हो सकते हैं। चूंकि इसे लगातार स्वैप करने होंगे, यह हर एक तत्व के लिए if कंडीशन को हिट करेगा। यिक्स! फिर से, इसे रिवर्स-सॉर्टेड सरणी पास करके और एक काउंटर वेरिएबल बनाकर प्रिंट आउट करके आज़माने के लिए स्वतंत्र महसूस करें।
हालांकि सबसे खराब स्थिति O(n^2) है, जो, जैसा कि आप याद कर सकते हैं, बबल सॉर्ट और सिलेक्शन सॉर्ट के लिए समान है, इंसर्शन सॉर्ट आमतौर पर बेहतर होता है। ऐसा इसलिए है क्योंकि, जैसा कि हमने देखा है, सबसे अच्छा मामला O(n) हो सकता है, जबकि सिलेक्शन सॉर्ट के लिए सबसे अच्छा मामला O(n^2) है। इंसर्शन सॉर्ट में बबल सॉर्ट की तुलना में कम स्वैप्स भी होते हैं, इसलिए यह यह लड़ाई जीतता है।
समेटना
मुझे आशा है कि यह पोस्ट मददगार रही है और आप इंसर्शन सॉर्ट के फायदे और नुकसान को समझने के साथ-साथ एल्गोरिदम कैसे कार्य करता है, इसके बारे में आश्वस्त महसूस करते हैं। यदि आप अभी भी और अधिक के लिए उत्सुक हैं, तो मैं इंसर्शन सॉर्ट के लिए विकिपीडिया पेज देखने की सलाह देता हूं।
