Java में इन्सर्शन सॉर्ट: एक कैसे-करें गाइड

Java इन्सर्शन सॉर्ट एक सूची में प्रत्येक आइटम का मूल्यांकन करता है। यदि कोई आइटम उससे पहले वाले से कम है, तो सॉर्ट आइटम्स को स्वैप कर देता है। अन्यथा, आइटम्स उसी स्थान पर रहते हैं और सूची में अगले दो आइटम्स की तुलना की जाती है।

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

प्रोग्रामिंग में, सूचियों को सॉर्ट करने के कुछ मानक तरीके हैं। हम इन्हें सॉर्ट एल्गोरिदम कहते हैं। सॉर्ट एल्गोरिदम सूची में सभी आइटम्स को पढ़ते हैं और निर्देशों के एक विशेष सेट का उपयोग करके उन्हें सॉर्ट करते हैं। आपके द्वारा सामना किए जाने वाले सबसे आम सॉर्ट एल्गोरिदम में से एक इन्सर्शन सॉर्ट है।

इस गाइड में, हम चर्चा करने जा रहे हैं कि Java इन्सर्शन सॉर्ट एल्गोरिदम को कैसे लागू किया जाए। हम रास्ते में एक उदाहरण के माध्यम से चलेंगे ताकि आप सीख सकें कि इस सॉर्ट के पीछे का लॉजिक कैसे काम करता है।

चलिए शुरू करते हैं!

Java इन्सर्शन सॉर्ट क्या है?

Java इन्सर्शन सॉर्ट कार्ड गेम में आपके हाथ में कार्ड्स को सॉर्ट करने के समान काम करता है। इन्सर्शन सॉर्ट्स सूची में प्रत्येक आइटम की जांच करते हैं और इसे इसके बाएं आइटम के साथ स्वैप करते हैं। चाहे कोई आइटम स्वैप हो यह इस बात पर निर्भर करता है कि आइटम पिछले आइटम्स से बड़ा है या छोटा।

एक पल के लिए कल्पना करें कि आप एक कार्ड गेम खेल रहे हैं – व्हिस्ट, रम्मी, जो भी हो। जब आप अपने कार्ड्स को सॉर्ट कर रहे होते हैं, तो आप क्या करते हैं?

आप बाएं से शुरू करेंगे और जांचेंगे कि दूसरा कार्ड सॉर्टेड है या नहीं। यदि वह कार्ड अंतिम से बड़ा है, तो उसे उसी स्थिति में रहना चाहिए। अन्यथा, उसे सूची में एक स्थान ऊपर जाना चाहिए।

आप अपने हाथ में हर कार्ड के माध्यम से जाएंगे और इस ऑपरेशन को तब तक करेंगे जब तक हर कार्ड अपने सही क्रम में दिखाई न दे।

इन्सर्शन सॉर्ट कब उपयोग करना चाहिए?

इन्सर्शन सॉर्ट्स का उपयोग तब किया जाता है जब बाएं केवल कुछ एलिमेंट्स होते हैं जिन्हें सॉर्ट करने की आवश्यकता होती है।

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

इन्सर्शन सॉर्ट एक सरल सॉर्टिंग एल्गोरिदम है जिसका अर्थ है कि यह शुरुआती लोगों के लिए सीखने के लिए अच्छा है।

इन्सर्शन सॉर्ट वॉकथ्रू

कार्ड्स के डेक को विज़ुअलाइज़ करना दुनिया में सबसे सहज नहीं है। आइए एक प्रोग्रामिंग उदाहरण के माध्यम से चलते हैं ताकि आप शुरू कर सकें। निम्न सूची पर विचार करें:

इस सूची में, हम मानते हैं कि पहला एलिमेंट सॉर्टेड है।

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

इस मामले में, 6, 8 से बड़ा नहीं है। इसका मतलब है कि 6 हमारी सूची में एक स्थिति पीछे चला जाएगा, और 8 एक स्थिति आगे बढ़ जाएगा:

अब हमें तीसरे एलिमेंट की तुलना उसके बाएं एलिमेंट्स से करने की आवश्यकता है: क्या 3, 8 से बड़ा है? नहीं, तो 8 दाईं ओर स्थिति बदलता है:

क्या 3, 6 से बड़ा है? नहीं, तो हम संख्या 6 को मूव करते हैं:

अब, हमें यह तुलना करनी होगी कि हमारी सूची में चौथा आइटम – अंतिम आइटम – उसकी बाईं ओर के हर दूसरे आइटम से बड़ा है या नहीं। इस मामले में, 9 उसके सामने आने वाले सभी आइटम्स से बड़ा है: 8, 6, और 3।

यहां वह एल्गोरिदम है जिसका उपयोग हमने अपनी सूची को सॉर्ट करने के लिए किया है:

• पहला एलिमेंट सॉर्टेड है।
• दूसरे आइटम की तुलना उसके बाएं आइटम से करें।
• यदि यह आइटम उसके बाएं मान से बड़ा है, तो आइटम उसी स्थान पर रहता है। अन्यथा, हम मान को बाएं ले जाते हैं।
• तब तक दोहराएं जब तक सभी आइटम्स क्रम में दिखाई न दें।

अब हमारे पास एक सॉर्टेड सरणी है। इन्सर्शन सॉर्ट्स एक समय में एक आइटम के माध्यम से सॉर्ट करते हैं। आइए चर्चा करें कि इस सॉर्टिंग एल्गोरिदम को Java में कैसे लागू किया जाए।

Java में इन्सर्शन सॉर्ट कैसे करें

तुलना की जा रही दो मानों में से उच्चतम मान को हर बार सॉर्ट फंक्शन चलाने पर एक स्थिति दाईं ओर डाला जाता है।

यह सब सैद्धांतिक शब्दों में बात करना ठीक है, लेकिन आप इसे Java में कैसे लागू करते हैं? यह एक अच्छा सवाल है। आइए एक क्लास लिखें जो छात्र ग्रेड की सूची पर इन्सर्शन सॉर्ट करता है।

Arrays लाइब्रेरी तैयार करें

आइए अपने Java प्रोग्राम में Arrays लाइब्रेरी आयात करके शुरू करें। एक बार सॉर्ट हो जाने पर हम इस लाइब्रेरी का उपयोग अपनी सूची को कंसोल पर प्रिंट करने के लिए करेंगे:

import java.util.Arrays;

सॉर्ट मेथड घोषित करें

हम एक मेथड घोषित करके शुरू करेंगे जो हमारी सूची के माध्यम से जाता है और हमारे डेटा को आरोही क्रम में सॉर्ट करता है:

class SortGrades {
  public static void insertionSort(int[] numbersToSort) {
    int itemCount = numbersToSort.length;
    for (int value = 1; value < itemCount; value++) {
      int key = numbersToSort[value];
      int last = value - 1;
      while (last >= 0 && key < numbersToSort[last]) {
        numbersToSort[last + 1] = numbersToSort[last];
        --last;
      }
      numbersToSort[last + 1] = key;
    }
  }
}

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

हमारे for लूप के भीतर, हमने दो वेरिएबल घोषित किए हैं: key और last।

"key" Java वेरिएबल ट्रैक करता है कि हम वर्तमान में कौन सा आइटम सॉर्ट कर रहे हैं। "last" वेरिएबल ट्रैक करता है कि आइटम के बाएं कितने आइटम्स को सॉर्ट किया जाना है।

हमारा प्रोग्राम "key" के मान की तुलना उसके बाएं प्रत्येक एलिमेंट से तब तक करेगा जब तक हमें एक छोटा एलिमेंट नहीं मिल जाता। यह हमारे Java "while" लूप में होता है।

मेन फंक्शन परिभाषित करें

जब हम इस कोड को चलाते हैं, तो कुछ नहीं होता। ऐसा इसलिए है क्योंकि हमने अभी तक अपना मेन फंक्शन परिभाषित नहीं किया है। आइए एक मेन फंक्शन परिभाषित करें जो एक int सरणी (संख्याओं की एक सरणी) को परिभाषित करता है। यह मेन फंक्शन उन संख्याओं को सॉर्ट करने के लिए हमारे द्वारा घोषित insertionSort() फंक्शन का उपयोग करता है। इस कोड को अपने इन्सर्शन सॉर्ट Java मेथड घोषित करने के बाद पेस्ट करें:

public static void main(String args[]) {
  int[] numbers = { 8, 6, 3, 9 };
  InsertionSort sortNumbers = new InsertionSort();
  sortNumbers.insertionSort(numbers);
  String arrayToString = Arrays.toString(numbers);
  System.out.println("Sorted list: " + arrayToString);
}

हमारे मेन मेथड में, हमने उन संख्याओं की एक सूची घोषित की है जिन्हें हम सॉर्ट करना चाहते हैं। हमने अपने InsertionSort() मेथड का एक इंस्टेंस बनाया है जिसे sortNumbers कहा जाता है। हम इस मेथड का उपयोग अपनी संख्याओं की सूची को आरोही क्रम में सॉर्ट करने के लिए करते हैं। यह मेथड हमारे "numbers" सरणी के अंदर मानों को बदलता है; हमने इसके मानों को संग्रहीत करने के लिए एक अलग सरणी घोषित नहीं की है।

अगला, हमने Arrays.toString() मेथड का उपयोग अपनी संख्या सरणी को स्ट्रिंग में बदलने के लिए किया है। हम सॉर्ट की गई सूची को कंसोल पर प्रिंट करते हैं।

जटिलता समीक्षा

इन्सर्शन सॉर्ट का औसत केस कॉम्प्लेक्सिटी O(n^2) है। यह तब होता है जब कोई एलिमेंट्स सॉर्टेड नहीं होते।

बेस्ट केस कॉम्प्लेक्सिटी तब होती है जब एक सरणी सॉर्टेड होती है। इससे O(n) की समय जटिलता प्राप्त होगी। ऐसा इसलिए है क्योंकि इन्सर्शन सॉर्ट में इनर लूप इस मामले में बिल्कुल नहीं चलेगा।

सबसे खराब स्थिति में, एक इन्सर्शन सॉर्ट O(n^2) पर परफॉर्म करता है। यह तब होता है जब एक सरणी आरोही या अवरोही क्रम में होती है और आप इसे उल्टे क्रम में सॉर्ट करना चाहते हैं (यानी आरोही से अवरोही)। इसमें हर एलिमेंट की तुलना अन्य सभी एलिमेंट्स से करना शामिल होगा।

निष्कर्ष

इन्सर्शन सॉर्ट्स डेटा को सॉर्ट करने की एक कुशल विधि है। इन्सर्शन सॉर्ट्स सूची में दूसरे से शुरू होने वाले मानों की तुलना करते हैं। यदि यह मान इसके बाएं वाले से बड़ा है, तो हमारी सूची नहीं बदलती। अन्यथा, मान को तब तक ले जाया जाता है जब तक इसके बाएं आइटम इससे कम न हो जाए।

अब आप Java में अपना खुद का इन्सर्शन सॉर्ट एल्गोरिदम लिखना शुरू करने के लिए तैयार हैं! यदि आप अधिक Java सीखने के संसाधन ढूंढ रहे हैं, तो हमारे How to Learn Java गाइड को देखें।