सम्मिलन क्रम: सी के साथ एल्गोरिथ्म, C++, Java, Python उदाहरण

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

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

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

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

सम्मिलन सॉर्ट के लिए एल्गोरिथ्म में निम्नलिखित महत्वपूर्ण विशेषताएं हैं:

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

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

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

सम्मिलन ऑपरेशन का छद्म कोड:

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

A[N-1] is the element to be inserted in the 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 डाला जाना है।

चरण 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++ सम्मिलन सॉर्ट के लिए कार्यक्रम

#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 इंसर्शन सॉर्ट के लिए

#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 सम्मिलन सॉर्ट के लिए कार्यक्रम

#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) है। सम्मिलन सॉर्ट अनुकूली सॉर्टिंग एल्गोरिदम में से एक है।

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

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

सम्मिलन सॉर्ट में तत्वों को सॉर्ट करने के लिए अतिरिक्त स्थान की आवश्यकता नहीं होती है, स्थान जटिलता स्थिर रहती है, अर्थात, 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(n2): जब सारणी आरोही क्रम में हो तो उसे अवरोही क्रम में क्रमबद्ध करना सबसे खराब स्थिति है।
• सर्वोत्तम स्थिति जटिलता: O(n): बेस्ट केस जटिलता तब होती है जब सरणी पहले से ही सॉर्ट की गई होती है, बाहरी लूप n बार चलता है जबकि आंतरिक लूप बिल्कुल नहीं चलता है। तुलनाओं की संख्या केवल n होती है। इसलिए, इस मामले में, जटिलता रैखिक होती है।
• औसत मामला जटिलता: O(n2): यह तब होता है जब किसी सारणी के तत्व अव्यवस्थित क्रम में होते हैं, जो न तो आरोही होता है और न ही अवरोही।

सारांश

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