मर्ज सॉर्ट तकनीक डिवाइड एंड कंकर तकनीक पर आधारित है। हम पूरे डेटा सेट को छोटे भागों में विभाजित करते हैं और उन्हें सॉर्टेड ऑर्डर में एक बड़े टुकड़े में मर्ज करते हैं। यह वर्स्ट केस के लिए भी बहुत प्रभावी है क्योंकि इस एल्गोरिदम का वर्स्ट केस के लिए भी लोअर टाइम कॉम्प्लेक्सिटी है।
लिंक्ड लिस्ट को मर्ज-सॉर्ट का उपयोग करके बहुत कुशलता से सॉर्ट किया जा सकता है। लिंक्ड लिस्ट के लिए मर्जिंग कार्य बहुत सरल है। हम उन्हें मर्ज करने के लिए बस लिंक्स को अपडेट कर सकते हैं। इस सेक्शन में हम देखेंगे कि इस दृष्टिकोण का उपयोग करके लिंक्ड लिस्ट को कैसे सॉर्ट करें।
मर्ज सॉर्ट तकनीक की जटिलता
टाइम कॉम्प्लेक्सिटी - सभी केस के लिए 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