रूबी के साथ चयन क्रम को समझना

नोट:यह रूबी के साथ अलग-अलग सॉर्टिंग एल्गोरिदम को देखने वाली श्रृंखला का भाग 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

अगला, हम अपना आंतरिक लूप बनाते हैं। यह पंक्ति कह रही है "नवें तत्व के लिए दूसरी स्थिति में तत्व के लिए, निम्नानुसार करें"। यदि आप .. . से परिचित नहीं हैं ऑपरेटर, यह प्रारंभ बिंदु से समापन बिंदु तक, समावेशी रूप से एक सीमा बनाता है। उदाहरण के लिए, 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

बढ़िया!

समझना कि चयन क्रम अक्षम क्यों है

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

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

रैपिंग अप

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