रूबी के साथ मर्ज सॉर्ट की खोज

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

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

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

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

आइए आरेख में उदाहरण के माध्यम से चलते हैं। हम [38, 27, 43, 3, 9, 82, 10] की एक सरणी से शुरू करते हैं और फिर सरणी को आधे में तब तक विभाजित करें जब तक कि हमारे पास एकल तत्व न रह जाएं।

1. हम शुरुआती सरणी को दो हिस्सों में विभाजित करते हैं:[38, 27, 43, 3] और [9, 82, 10] ।
2. हमने पहले हाफ को फिर से विभाजित किया:[38, 27] और [43, 3] ।
3. हमने पहली छमाही को एकल तत्वों में विभाजित किया:[38] , [27] , [43] , और [3] ।
4. हम 38 और 27 को [27, 38] . बनाने के लिए सॉर्ट करते हैं और 48 और 3 [3, 43] . बनाने के लिए ।
5. इन्हें एक साथ रखने पर, हमारे पास [3, 27, 38, 43] . है ।
6. अब, हम मूल सरणी के दूसरे भाग में जाते हैं, जो [9, 82, 10] था। . हम इसे आधे में विभाजित करते हैं और [9, 82] . प्राप्त करते हैं और [10] ।
7. हम विभाजित करते हैं [9, 82] [9] . में और [82] , और फिर हमारे पास [10] . है , जो पहले से ही एकवचन है।
8. हम [9, 82] को क्रमबद्ध करते हैं वापस एक साथ और फिर [10] को मर्ज करें वापस, जिसके परिणामस्वरूप [9, 10, 82] ।
9. आखिरकार, हम [3, 27, 38, 43] को मर्ज करते हैं और [9, 10, 82] [3, 9, 10, 27, 38, 43, 82] पाने के लिए ।

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

रूबी में लिखा गया मर्ज सॉर्ट एल्गोरिथम निम्नलिखित है:

class MergeSort
  def sort(numbers)

    num_elements = numbers.length
    if num_elements <= 1
      return numbers
    end

    half_of_elements = (num_elements / 2).round

    left  = numbers.take(half_of_elements)
    right = numbers.drop(half_of_elements)

    sorted_left = sort(left)
    sorted_right = sort(right)

    merge(sorted_left, sorted_right)
  end

  def merge(left_array, right_array)
    if right_array.empty?
      return left_array
    end

    if left_array.empty?
      return right_array
    end

    smallest_number = if left_array.first <= right_array.first
      left_array.shift
    else
      right_array.shift
    end

    recursive = merge(left_array, right_array)

    [smallest_number].concat(recursive)
  end
end

आइए चलते हैं यहां क्या हो रहा है। सबसे पहले, हम sort . पर ध्यान देंगे शीर्ष पर विधि।

  def sort(numbers)

    num_elements = numbers.length
    if num_elements <= 1
      return numbers
    end

    half_of_elements = (num_elements / 2).round

    left  = numbers.take(half_of_elements)
    right = numbers.drop(half_of_elements)

    sorted_left = sort(left)
    sorted_right = sort(right)

    merge(sorted_left, sorted_right)
  end

कोड के इस हिस्से का लक्ष्य दी गई संख्याओं को आधे में विभाजित करना है जब तक कि हमारे पास प्रत्येक में केवल एक आइटम न रह जाए। इसे क्रिया में देखने के लिए, अंतिम पंक्ति पर टिप्पणी करें (मर्ज (सॉर्टेड_लेफ्ट, सॉर्टेड_राइट)) और, इसके बजाय, प्रिंट आउट sorted_left और sorted_right . हमारे उदाहरण सरणी में पास करके प्रोग्राम चलाना, आपको इसे अपने टर्मिनल में देखना चाहिए:

merge_sort = MergeSort.new
puts merge_sort.sort([38, 27, 43, 3, 9, 82, 10])

ruby ruby-merge-sort.rb

27
43
38

3
9
82
10

महान! हमारे कोड ने हमारी प्रारंभिक सरणी ले ली है और इसे आधे में विभाजित कर दिया है। आइए एक नज़र डालते हैं merge . पर कोड का अगला भाग।

  def merge(left_array, right_array)
    if right_array.empty?
      return left_array
    end

    if left_array.empty?
      return right_array
    end

    smallest_number = if left_array.first <= right_array.first
      left_array.shift
    else
      right_array.shift
    end

    recursive = merge(left_array, right_array)

    [smallest_number].concat(recursive)
  end

सबसे पहले, हम जांचते हैं कि कोई उप-सरणी खाली है या नहीं। यदि ऐसा है, तो हम बस दूसरे को वापस कर सकते हैं। अन्यथा, यह देखते हुए कि दोनों उप-सरणी खाली नहीं हैं, हम प्रत्येक सरणी के पहले तत्व के मान की तुलना करते हैं और फिर अनंत लूप के निर्माण को रोकने के लिए तुलनात्मक मानों को स्थानांतरित करते हैं। इसके बाद, हम मूल सरणी पर पुनरावर्तन (उस पर एक सेकंड में अधिक!) का उपयोग करते हैं जब तक कि हम अंत में दो सरणियों को एक साथ जोड़ नहीं सकते, अच्छी तरह से क्रमबद्ध।

पुनरावृत्ति पर थोड़ा अधिक

अगर कुछ ऐसा है जो हमारे कोड में अजीब लगता है, तो मेरा अनुमान है कि यह यह पंक्ति है:recursive = merge(left_array, right_array) हम अपने merge . को कॉल कर रहे हैं स्वयं के भीतर . से विधि . वाह! इसे हम रिकर्सन कहते हैं - एक ऐसी तकनीक जिसमें कोई फंक्शन खुद को एक या अधिक बार कॉल करता है जब तक कि एक निर्दिष्ट शर्त पूरी नहीं हो जाती। हमारे मामले में, merge बाएँ या दाएँ सरणी खाली होने तक कॉल करना जारी रहेगा। यदि आप पुनरावर्तन के बारे में अधिक जानने में रुचि रखते हैं, तो यहां एक उदाहरण दिया गया है जो एक फिबोनाची अनुक्रम के लिए एक फ़ंक्शन लिखने के लिए रूबी और रिकर्सन के उपयोग के माध्यम से चलता है।

रैप-अप

मुझे आशा है कि आपको मर्ज सॉर्ट के बारे में और जानने में मज़ा आया होगा! यह समझना कि यह उच्च स्तर पर कैसे काम करता है, साथ ही यह बबल या चयन प्रकार की तुलना में अधिक कुशल विकल्प क्यों है, संभवतः नौकरी के साक्षात्कार या आपके दिन-प्रतिदिन के कार्यों में काम आएगा। इसके अलावा, कई मर्ज सॉर्ट वेरिएंट हैं जिनके बारे में आप विकिपीडिया पर अधिक पढ़ सकते हैं यदि आप रुचि रखते हैं। अगली बार तक ... हैप्पी सॉर्टिंग!