सी भाषा में इंसर्शन सॉर्ट एल्गोरिथम C++, Java, Python उदाहरण

सम्मिलन सॉर्ट क्या है?

इंसर्शन सॉर्ट, तुलनात्मक सॉर्टिंग एल्गोरिदम में से एक है जिसका उपयोग तत्वों को सॉर्ट करने के लिए किया जाता है, जिसमें एक समय में एक तत्व पर पुनरावृति की जाती है और तत्व को पहले से व्यवस्थित क्षेत्र के भीतर उसके सही स्थान पर रखा जाता है।

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

क्योंकि इंसर्शन सॉर्ट परिणाम को क्रमिक रूप से बनाता है, इसलिए इसे सिखाना सहज है, इसमें मौजूद त्रुटियों को दूर करना आसान है, और यह बहुत छोटे इनपुट के लिए एक मजबूत आधार है जहां अधिक जटिल एल्गोरिदम मापने योग्य लाभ के बिना अतिरिक्त भार बढ़ा देंगे।

सम्मिलन सॉर्ट एल्गोरिथ्म की विशेषताएं

इंसर्शन सॉर्ट एल्गोरिदम में निम्नलिखित महत्वपूर्ण विशेषताएं हैं जो वास्तविक कार्यभार पर इसके व्यवहार की व्याख्या करती हैं:

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

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

इन्सर्ट कैसे होता है? Operaक्या आप काम करना चाहते हैं?

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

इन्सर्ट ऑपरेशन का स्यूडोकोड:

N तत्वों की एक सूची A पर विचार करें।

// Insert A[N-1] into sorted sublist A[0..N-2]
for i = N-1 to 1:
    if A[i] < A[i-1], then swap A[i] and A[i-1]
    else stop

ऊपर दिए गए उदाहरण में, पहले से क्रमबद्ध सूची में एक नया तत्व 6 डाला गया है। निम्नलिखित चरणों का पालन करें। tracजैसे ही नया तत्व अपनी सही स्थिति की ओर बाईं ओर बढ़ता है, आंतरिक लूप में गति उत्पन्न होती है।

चरण 1) A[5] के बाएँ आसन्न तत्व, 9 > 6 की तुलना में, हम 9 और 6 की स्थिति को बदलते हैं। अब तत्व 6 को A[4] में ले जाया गया है।

चरण 2) अब, हम A[4] और A[3] की तुलना करते हैं, और हम पाते हैं कि A[3] > A[4], इसलिए हम फिर से 6 और 8 की स्थिति को बदल देते हैं।

चरण 3) अब A[3] और A[2] की तुलना करें। चूंकि A[2] > A[3], हम 7 और 6 की स्थिति को आपस में बदल देते हैं।

चरण 4) हम A[1] और A[2] की तुलना करते हैं। चूंकि A[1] < A[2] है, इसलिए बाएँ से सटा हुआ तत्व अब बड़ा नहीं है। हम यह निष्कर्ष निकालते हैं कि 6 सही ढंग से डाला गया है, और हम आंतरिक लूप को यहीं रोकते हैं।

सम्मिलन सॉर्ट कैसे काम करता है

ऊपर वर्णित इंसर्ट ऑपरेशन, इंसर्शन सॉर्ट का आधार है। इंसर्ट प्रक्रिया प्रत्येक तत्व पर निष्पादित होती है, और अंत में, हमें सॉर्ट की गई सूची प्राप्त होती है क्योंकि प्रत्येक बाहरी पास पर सॉर्ट किया गया क्षेत्र एक तत्व से बढ़ता जाता है।

ऊपर दिया गया चित्र डेटा संरचना में इंसर्शन सॉर्ट की कार्यप्रणाली को दर्शाता है। प्रारंभ में, सॉर्ट की गई उपसूची में केवल एक तत्व है, अर्थात् 4। A[1], अर्थात् 3, को सम्मिलित करने के बाद, सॉर्ट की गई उपसूची का आकार बढ़कर 2 हो जाता है, और एल्गोरिदम इस प्रक्रिया को तब तक जारी रखता है जब तक कि प्रत्येक तत्व को उसमें शामिल नहीं कर लिया जाता।

वैचारिक प्रवाह स्थापित होने के बाद, निम्नलिखित अनुभाग ठोस कार्यान्वयनों को दर्शाते हैं। C++, सी, और Python ताकि आप विभिन्न भाषाओं में लूप संरचनाओं की तुलना कर सकें।

C++ सम्मिलन सॉर्ट के लिए कार्यक्रम

RSI C++ नीचे दिए गए कार्यान्वयन में दो नेस्टेड लूप का उपयोग किया गया है: बाहरी लूप अगले अव्यवस्थित तत्व का चयन करता है, और आंतरिक लूप इसे तब तक बाईं ओर स्थानांतरित करता है जब तक कि सही स्थिति नहीं मिल जाती।

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    return 0;
}

आउटपुट:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code इंसर्शन सॉर्ट के लिए

यही तर्क सीधे C भाषा पर भी लागू होता है। मानक printf कॉल स्ट्रीम आउटपुट को प्रतिस्थापित करते हैं, लेकिन आंतरिक लूप के अंदर स्वैप पैटर्न समान होता है। C++ संस्करण.

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

आउटपुट:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Python सम्मिलन सॉर्ट के लिए कार्यक्रम

Python टपल स्वैप का समर्थन करता हैping एक ही अभिव्यक्ति में, इसलिए आंतरिक लूप इसके C की तुलना में अधिक कॉम्पैक्ट है और C++ समान एल्गोरिथम व्यवहार को बनाए रखते हुए समकक्षों का उपयोग करना।

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

आउटपुट:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

सम्मिलन सॉर्ट के गुण

इंसर्शन सॉर्ट की कुछ महत्वपूर्ण विशेषताएं यहां दी गई हैं जो आपको यह तय करने में मदद करती हैं कि यह कब सही उपकरण है:

• ऑनलाइन: इंसर्शन सॉर्ट तत्वों को प्राप्त होते ही सॉर्ट कर सकता है। यदि हमने पहले से ही तत्वों की सूची को सॉर्ट कर लिया है और उसमें और तत्व जोड़ते हैं, तो हमें पूरी सॉर्टिंग प्रक्रिया को दोबारा चलाने की आवश्यकता नहीं है। इसके बजाय, हम केवल नए जोड़े गए तत्वों पर ही इटरेट करते हैं।
• जगह में: इंसर्शन सॉर्ट एल्गोरिदम की स्पेस कॉम्प्लेक्सिटी स्थिर है और इसके लिए अतिरिक्त स्पेस की आवश्यकता नहीं होती है। यह एल्गोरिदम तत्वों को उनके स्थान पर ही सॉर्ट करता है।
• स्थिर: इंसर्शन सॉर्ट में, यदि तत्वों के मान बराबर हों तो हम उन्हें आपस में नहीं बदलते। उदाहरण के लिए, यदि दो तत्व x और y बराबर हैं और अव्यवस्थित सूची में x, y से पहले आता है, तो क्रमबद्ध सूची में भी x, y से पहले ही आएगा। यही कारण है कि इंसर्शन सॉर्ट स्थिर होता है।
• अनुकूली: A छँटाई एल्गोरिथ्म यदि इनपुट तत्व या तत्वों का एक उपसमूह पहले से ही क्रमबद्ध हो तो कम समय लेने वाला इंसर्शन सॉर्ट एक अनुकूली सॉर्टिंग एल्गोरिदम कहलाता है। जैसा कि हमने ऊपर चर्चा की है, इंसर्शन सॉर्ट का सर्वोत्तम रनिंग टाइम O(N) है और सबसे खराब रनिंग टाइम O(N^2) है। इंसर्शन सॉर्ट एक अनुकूली सॉर्टिंग एल्गोरिदम है।

सम्मिलन क्रम की जटिलता

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

अंतरिक्ष जटिलता

इंसर्शन सॉर्ट में तत्वों को सॉर्ट करने के लिए अतिरिक्त स्थान की आवश्यकता नहीं होती है। इसकी स्पेस कॉम्प्लेक्सिटी स्थिर होती है, यानी O(1), क्योंकि इनपुट आकार चाहे जो भी हो, केवल कुछ ही अस्थायी चर उपयोग किए जाते हैं।

समय जटिलता

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

• पास 1 के लिए, आवश्यक न्यूनतम स्वैप शून्य हैं, और आवश्यक अधिकतम स्वैप 1 हैं।
• पास 2 के लिए, आवश्यक न्यूनतम स्वैप शून्य हैं, और आवश्यक अधिकतम स्वैप 2 हैं।
• पास N के लिए, आवश्यक न्यूनतम स्वैप शून्य है, और आवश्यक अधिकतम स्वैप N हैं।
• न्यूनतम स्वैप शून्य है, इसलिए N पासों की पुनरावृत्ति के लिए सर्वोत्तम समय जटिलता O(N) है।
• कुल अधिकतम स्वैप (1+2+3+4+…+N) हैं, यानी N(N+1)/2, इसलिए सबसे खराब समय जटिलता O(N^2) है।

यहां इंसर्शन सॉर्ट की महत्वपूर्ण समय जटिलता दी गई है:

• सबसे खराब स्थिति जटिलता: O(n^2): किसी ऐरे को अवरोही क्रम में सॉर्ट करना जबकि उसे आरोही क्रम में सॉर्ट करना आवश्यक है, सबसे खराब स्थिति है।
• सर्वोत्तम स्थिति जटिलता: O(n): सबसे अच्छा मामला तब होता है जब ऐरे पहले से ही सॉर्ट किया हुआ हो; बाहरी लूप n बार चलता है, जबकि आंतरिक लूप बिल्कुल नहीं चलता। केवल n तुलनाएँ होती हैं, इसलिए जटिलता रैखिक होती है।
• औसत मामला जटिलता: O(n^2): यह तब होता है जब ऐरे के तत्व अव्यवस्थित क्रम में होते हैं जो न तो आरोही क्रम में होते हैं और न ही अवरोही क्रम में।

अक्सर पूछे जाने वाले प्रश्न