Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: लिंक्ड लिस्ट पर मर्ज सॉर्ट एल्गोरिदम इम्प्लीमेंट करना


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

लिंक्ड लिस्ट को मर्ज-सॉर्ट का उपयोग करके बहुत कुशलता से सॉर्ट किया जा सकता है। लिंक्ड लिस्ट के लिए मर्जिंग कार्य बहुत सरल है। हम उन्हें मर्ज करने के लिए बस लिंक्स को अपडेट कर सकते हैं। इस सेक्शन में हम देखेंगे कि इस दृष्टिकोण का उपयोग करके लिंक्ड लिस्ट को कैसे सॉर्ट करें।

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

  • टाइम कॉम्प्लेक्सिटी - सभी केस के लिए O(n log n)

  • स्पेस कॉम्प्लेक्सिटी - O(n)

इनपुट - अनसॉर्टेड लिस्ट: 14 20 78 98 20 45
आउटपुट - सॉर्टिंग के बाद ऐरे: 14 20 20 45 78 98

एल्गोरिदम

mergeList(ll1, ll2)

इनपुट - यह दो लिंक्ड लिस्ट ll1 और ll2 लेता है

आउटपुट - मर्ज की गई लिस्ट

Begin
    यदि ll1 खाली है, तो ll2 लौटाएं
    यदि ll2 खाली है, तो ll1 लौटाएं
    यदि data(ll1) <= data(ll2), तो
        new_head = ll1;
        next(new_head) = mergeList(next(ll1), ll2)
    अन्यथा
        new_head = ll2;
        next(new_head) = mergeList(ll1, next(ll2))
    new_head लौटाएं
End

split_list(start, ll1, ll2)

इनपुट - एक लिंक्ड लिस्ट का स्टार्ट पॉइंट, दो आउटपुट आर्गुमेंट्स ll1 और ll2

आउटपुट - लिंक्ड लिस्ट से जनरेटेड दो लिंक्ड लिस्ट

Begin
    slow := start
    fast := next(start)
    जब तक fast नल नहीं है, करें
        fast := next(fast)
        यदि fast नल नहीं है, तो
            slow := next(slow)
            fast := next(fast)
    लूप समाप्त
    ll1 := start
    ll2 := next(slow)
    next(slow) := null
End

mergeSort(start)

इनपुट - लिंक्ड लिस्ट

आउटपुट - सॉर्टेड लिंक्ड लिस्ट

Begin
    head = start
    यदि head नल है या next(head) नल है, तो लौटाएं
    split_list(head, ll1, ll2)
    mergeSort(ll1)
    mergeSort(ll2)
    start := mergeList(ll1, ll2)
End

सोर्स कोड (C++)

#include <bits/stdc++.h>
using namespace std;

class node { // डेटा और अगला एड्रेस स्टोर करने के लिए नोड परिभाषित करें
public:
    int data;
    node *next;
};

void display(class node* start) {
    node* p = start; // करंट नोड को हेड पर सेट करें
    while (p != NULL) { // तब तक ट्रैवर्स करें जब तक करंट नोड NULL न हो
        cout << p->data << " ";
        p = p->next; // अगले नोड पर जाएं
    }
}

node* getNode(int d) {
    node* temp = new node;
    temp->data = d;
    temp->next = NULL;
    return temp;
}

node* mergeList(node* ll1, node* ll2) { // दो सॉर्टेड लिस्ट मर्ज करने का फंक्शन
    node* newhead = NULL;
    if (ll1 == NULL)
        return ll2;
    if (ll2 == NULL)
        return ll1;
    // रिकर्सिवली लिस्ट्स मर्ज करें
    if (ll1->data <= ll2->data) {
        newhead = ll1;
        newhead->next = mergeList(ll1->next, ll2);
    } else {
        newhead = ll2;
        newhead->next = mergeList(ll1, ll2->next);
    }
    return newhead;
}

void splitList(node* start, node** ll1, node** ll2) {
    // फ्लॉयड के टॉरटॉइज एल्गोरिदम के समान
    node* slow = start;
    node* fast = start->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    *ll1 = start;
    *ll2 = slow->next; // विभाजन
    slow->next = NULL;
}

void mergeSort(node** start) {
    node* head = *start;
    node *ll1, *ll2;
    // बेस केस
    if (head == NULL || head->next == NULL) {
        return;
    }
    splitList(head, &ll1, &ll2); // लिस्ट को दो हिस्सों में विभाजित करें
    // लेफ्ट और राइट सबलिस्ट को सॉर्ट करें
    mergeSort(&ll1);
    mergeSort(&ll2);
    // दो सॉर्टेड लिस्ट मर्ज करें
    *start = mergeList(ll1, ll2);
    return;
}

int main() {
    cout << "Creating the linked list: " << endl;
    cout << "Enter 0 to stop building the list, else enter any integer" << endl;
    int k, count = 1, x;
    node* curr, *temp;
    cin >> k;
    node* head = getNode(k); // लिस्ट बनाना, पहला नोड
    cin >> k;
    temp = head;
    while (k) {
        curr = getNode(k);
        temp->next = curr; // प्रत्येक नोड को जोड़ना
        temp = temp->next;
        cin >> k;
    }
    cout << "Before sorting: " << endl;
    display(head); // लिस्ट प्रदर्शित करना
    cout << "\nAfter sorting: " << endl;
    mergeSort(&head);
    display(head);
    return 0;
}

आउटपुट

Creating the linked list:
Enter 0 to stop building the list, else enter any integer
89 54 15 64 74 98 10 24 26 0
Before sorting: 89 54 15 64 74 98 10 24 26
After sorting: 10 15 24 26 54 64 74 89 98

  1. C++ प्रोग्राम: एडजेसेंसी लिस्ट इम्प्लीमेंट करना C++ प्रोग्राम: एडजेसेंसी लिस्ट इम्प्लीमेंट करना

    एक ग्राफ का एडजेसेंसी लिस्ट प्रतिनिधित्व एक लिंक्ड लिस्ट प्रतिनिधित्व है। इस प्रतिनिधित्व में हमारे पास लिस्ट्स का एक ऐरे होता है। ऐरे का आकार V होता है। यहां V वर्टेक्स की संख्या है। दूसरे शब्दों में, हम कह सकते हैं कि हमारे पास V संख्या की अलग-अलग लिस्ट्स को स्टोर करने के लिए एक ऐरे है। यदि एक लि

  1. - C++ प्रोग्राम: सर्कुलर सिंगली लिंक्ड लिस्ट कार्यान्वयन

    सर्कुलर सिंगली लिंक्ड लिस्ट अंतिम नोड पहले नोड (head) को इंगित करता है, जिससे एक वृत्त बनता है। केवल head संदर्भ से पूरी सूची एक्सेस की जा सकती है। C++ प्रोग्राम उदाहरण next; } while (ptr != head); } int main() { insert(3); insert(1); insert(7); insert(2); insert(9); c

  1. - C++ प्रोग्राम: सिंगली लिंक्ड लिस्ट कार्यान्वयन

    सिंगली लिंक्ड लिस्ट प्रत्येक नोड में डेटा और अगले नोड का संदर्भ होता है। अंतिम नोड NULL इंगित करता है। केवल head से पूरी सूची एक्सेस की जा सकती है। C++ प्रोग्राम उदाहरण next; } } int main() { insert(3); insert(1); insert(7); insert(2); insert(9); cout << The link