মার্জ সোর্ট টেকনিক ডিভাইড এন্ড কনকর টেকনিকের উপর ভিত্তি করে। আমরা পুরো ডেটা সেটকে ছোট ছোট অংশে ভাগ করি এবং সেগুলো সর্টেড অর্ডারে মার্জ করে বড় پیস বানাই। এটি ওয়ার্স্ট কেসের জন্যও খুব ইফেক্টিভ কারণ এই অ্যালগরিদমের ওয়ার্স্ট কেসের টাইম কমপ্লেক্সিটি কম।
লিংকড লিস্ট মার্জ সোর্ট ব্যবহার করে খুব ইফিশিয়েন্টলি সর্ট করা যায়। লিংকড লিস্টের জন্য মার্জিং টাস্ক খুব সিম্পল। আমরা সিম্পলি লিংকগুলো আপডেট করে সেগুলো মার্জ করতে পারি। এই সেকশনে আমরা দেখব কীভাবে লিংকড লিস্টকে এই আপরোচ দিয়ে সর্ট করা হয়।
মার্জ সোর্ট টেকনিকের কমপ্লেক্সিটি
টাইম কমপ্লেক্সিটি - সব কেসের জন্য O(n log n)
স্পেস কমপ্লেক্সিটি - O(n)
ইনপুট - অনসর্টেড লিস্ট: 14 20 78 98 20 45 আউটপুট - সর্টিং után অ্যারে: 14 20 20 45 78 98
অ্যালগরিদম
mergeList(ll1, ll2)
ইনপুট - দুটি লিংকড লিস্ট ll1 এবং ll2 নেয়
আউটপুট - মার্জ করা লিস্ট
শুরু if ll1 খালি, তবে return ll2 if ll2 খালি, তবে return ll1 if data(ll1) <= data(ll2), then new_head = ll1; next(new_head) = mergeList(next(ll1), ll2) else new_head = ll2; next(new_head) = mergeList(ll1, next(ll2)) return new_head শেষ
split_list(start, ll1, ll2)
ইনপুট - একটি লিংকড লিস্টের স্টার্ট পয়েন্টার, দুটি আউটপুট আর্গুমেন্ট ll1 এবং ll2
আউটপুট - লিংকড লিস্ট থেকে জেনারেটেড দুটি লিংকড লিস্ট
শুরু
slow := start
fast := next(start)
যতক্ষণ fast null নয়, করুন
fast := next(fast)
if fast null নয়, তবে
slow := next(slow)
fast := next(fast)
লুপ শেষ
ll1 := start
ll2 := next(slow)
next(slow) := null
শেষ
mergeSort(start)
ইনপুট - লিংকড লিস্ট
আউটপুট - সর্টেড লিংকড লিস্ট
শুরু head = start if head null বা next(head) null, তবে return split_list(head, ll1, ll2) mergeSort(ll1) mergeSort(ll2) start := mergeList(ll1, ll2) শেষ
সোর্স কোড (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); // লিস্টকে দুই হälfte ভাগ করুন
// লেফট এবং রাইট সাবলিস্ট সর্ট করুন
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
