रूबी में सिलेक्शन सॉर्ट में महारत: चरण-दर-चरण कार्यान्वयन

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

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

उच्च स्तर पर, सिलेक्शन सॉर्ट सरणी को दो भागों में विभाजित करता है: एक आधा सॉर्टेड और दूसरा नहीं। शुरुआत में, सॉर्टेड सेक्शन खाली होता है, और अनसॉर्टेड भाग में सभी तत्व होते हैं। सिलेक्शन सॉर्ट दो लूप्स का उपयोग करता है; बाहरी लूप n बार पुनरावृति करता है, जहां n सरणी में तत्वों की संख्या है। हम तुरंत "मिन इंडेक्स" को पहले तत्व पर सेट करते हैं, और फिर तुलना करने के लिए एक और लूप का उपयोग करते हैं, यदि आसन्न तत्व वर्तमान न्यूनतम से कम है तो मिन इंडेक्स को स्वैप करते हैं।

यदि इसका पालन करना कठिन है, तो चिंता न करें! हम अगले एक वास्तविक उदाहरण के माध्यम से चलने जा रहे हैं। :)

चरण-दर-चरण

निम्नलिखित तत्वों के साथ एक सरणी से शुरू करते हैं: [10, 30, 27, 7, 33, 15, 40, 50]

पहली पुनरावृत्ति: सबसे छोटी संख्या ढूंढें

इस मामले में, सबसे छोटी संख्या 7 है, इसलिए हम इसे शुरुआत में रखते हैं और 10 को वहां ले जाते हैं जहां 7 था। हमारी सरणी अब इस तरह दिखती है: [7, 30, 27, 10, 33, 15, 40, 50]

दूसरी पुनरावृत्ति: अगली सबसे छोटी संख्या ढूंढें

इंडेक्स पोजीशन 1 में तत्व से शुरू करते हुए (याद रखें, सरणी 0-इंडेक्स्ड हैं), अगला सबसे छोटा तत्व ढूंढें

इस मामले में, यह 10. है। 10 को सरणी में दूसरी स्थिति में ले जाएं और 30 को वहां ले जाएं जहां 10 था। परिणामी सरणी यह है: [7, 10, 27, 30, 33, 15, 40, 50]

यहां से, हम इस सटीक प्रक्रिया को तब तक जारी रखते हैं जब तक हमारी सरणी पूरी तरह से सॉर्ट न हो जाए। नीचे, आप अगली पुनरावृत्तियों के बाद परिणामी सरणी देख सकते हैं।

तीसरी पुनरावृत्ति:

[7, 10, 15, 30, 33, 27, 40, 50]

चौथी पुनरावृत्ति:

[7, 10, 15, 27, 33, 30, 40, 50]

पांचवीं पुनरावृत्ति:

[7, 10, 15, 27, 30, 33, 40, 50]

बिंगो! हम सॉर्ट हो गए!

यदि आप अधिक विजुअल लर्नर हैं, तो यहां एक उदाहरण है कि [] की सरणी के साथ सिलेक्शन सॉर्ट कैसे काम करेगा

फोटो क्रेडिट

एक रूबी कार्यान्वयन

यहां रूबी में लिखा गया एक सिलेक्शन सॉर्ट फंक्शन है:

def selection_sort(array) 
  n = array.length - 1 
  n.times do |i| 
    min_index = i 
    for j in (i + 1)..n 
      min_index = j if array[j] < array[min_index] 
    end 
    array[i], array[min_index] = array[min_index], array[i] if min_index != i 
  end 
  puts array 
end 

आइए देखें कि यह कैसे काम करता है।

सबसे पहले, हम n को तत्वों की संख्या के बराबर सेट करते हैं। याद रखें, हमें एक घटाना होगा क्योंकि सरणी 0-इंडेक्स्ड हैं।

अगला, हम अपना बाहरी लूप बनाते हैं, जो n बार चलने वाला है।

min_index = i 

यहां, हम न्यूनतम इंडेक्स को पहले स्थान पर तत्व पर सेट कर रहे हैं।

for j in (i + 1)..n 

अगला, हम अपना आंतरिक लूप बनाते हैं। यह लाइन कह रही है "दूसरी स्थिति में तत्व से nth तत्व तक, जो अनुसरण करता है वह करें"। यदि आप .. ऑपरेटर से परिचित नहीं हैं, तो यह प्रारंभ बिंदु से अंत बिंदु तक, समावेशी रूप से एक रेंज बनाता है। उदाहरण के लिए, 1..10 1 से 10 तक, समावेशी, एक रेंज बनाता है।

min_index = j if array[j] < array[min_index] 

इस लूप के अंदर, हम min_index को एक नए तत्व पर सेट करते हैं यदि यह वर्तमान min_index से कम है।

array[i], array[min_index] = array[min_index], array[i] if min_index != i 

हमारे आंतरिक लूप के बाहर, हम यह देखने के लिए जांचते हैं कि क्या वर्तमान min_index i के बराबर है। यदि यह सच है, तो हमें अपने तत्वों को शफल करने की आवश्यकता है। हम array[i] को array[min_index] पर सेट करते हैं और array[min_index] को array[i] पर। यहां, हम वही "स्वैप" कर रहे हैं जो हमने अपने उदाहरण में किया था।

अंत में, एक बार जब हम समाप्त कर लेते हैं, तो हम अपनी सरणी को आउटपुट करते हैं, जो अब सॉर्ट हो गई है!

इसे एक साथ रखना

यहां मेरा पूरा प्रोग्राम है:

def selection_sort(array) 
  n = array.length - 1 
  n.times do |i| 
    min_index = i 
    for j in (i + 1)..n 
      min_index = j if array[j] < array[min_index] 
    end 
    array[i], array[min_index] = array[min_index], array[i] if min_index != i 
  end 
  puts array 
end 

array = [10, 30, 27, 7, 33, 15, 40, 50] 
selection_sort(array) 

टर्मिनल से ruby ruby-selection-sort.rb चलाने पर निम्नलिखित आउटपुट होता है:

7 
10 
15 
27 
30 
33 
40 
50 

कूल!

यह समझना कि सिलेक्शन सॉर्ट अक्षम क्यों है

एक एल्गोरिदम की दक्षता को मापने का एक तरीका "बिग-ओ नोटेशन" को देखना है; यह सबसे खराब स्थिति के प्रदर्शन को दर्शाता है ताकि एल्गोरिदम की तुलना की जा सके। उदाहरण के लिए, O(1) के बिग-ओ वाला एक एल्गोरिदम का मतलब है कि सबसे खराब स्थिति का रन टाइम तत्वों की संख्या, "n", के बढ़ने के साथ स्थिर है, जबकि O(n) के बिग-ओ नोटेशन वाला एक एल्गोरिदम का मतलब है कि सबसे खराब स्थिति का रन टाइम n के बढ़ने के साथ रैखिक रूप से बढ़ता है। इसका मतलब है कि यदि आपके पास 100 तत्वों वाली एक सरणी है और O(n) और O(1) सॉर्टिंग एल्गोरिदम के बीच चयन करना है, तो आप O(1) एल्गोरिदम चुनेंगे क्योंकि O(1) निश्चित रूप से O(100) को हरा देता है।

बबल सॉर्ट की तरह, सिलेक्शन सॉर्ट का सबसे खराब स्थिति और औसत जटिलता O(n^2) है क्योंकि नेस्टेड लूप्स के कारण। इसका मतलब है कि तत्वों की संख्या बढ़ने के साथ इसकी दक्षता नाटकीय रूप से घट जाती है।

निष्कर्ष

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