লিংকড লিস্টে মার্জ সর্ট অ্যালগরিদম বাস্তবায়নের জন্য C++ প্রোগ্রাম

মার্জ বাছাই কৌশলটি ভাগ করুন এবং জয় করুন কৌশলের উপর ভিত্তি করে৷ আমরা যখন ডেটা সেটকে ছোট ছোট অংশে ভাগ করি এবং সাজানো ক্রমে একটি বড় অংশে একত্রিত করি। এটি সবচেয়ে খারাপ ক্ষেত্রেও খুব কার্যকর কারণ এই অ্যালগরিদমের সবচেয়ে খারাপ ক্ষেত্রেও কম সময়ের জটিলতা রয়েছে৷

সংযুক্ত তালিকা মার্জ-সর্ট ব্যবহার করে খুব দক্ষতার সাথে সাজানো যায়। লিঙ্ক করা তালিকার জন্য মার্জিং টাস্ক খুবই সহজ। আমরা সহজভাবে লিঙ্কগুলিকে একত্রিত করতে আপডেট করতে পারি। এই বিভাগে আমরা দেখব কিভাবে এই পদ্ধতি ব্যবহার করে লিঙ্ক করা তালিকা সাজাতে হয়।

মার্জ সাজানোর কৌশলের জটিলতা

• সময়ের জটিলতা − O(n log n) সমস্ত ক্ষেত্রে

• মহাকাশের জটিলতা − O(n)

ইনপুট − সাজানো তালিকা:14 20 78 98 20 45আউটপুট − সাজানোর পর অ্যারে:14 20 20 45 78 98 

অ্যালগরিদম

মার্জলিস্ট(ll1, ll2)

ইনপুট − এটি দুটি লিঙ্কযুক্ত তালিকা ll1 এবং ll2

আউটপুট - একত্রিত তালিকা

শুরু করুন যদি ll1 খালি থাকে, তারপর ll2 রিটার্ন করুন যদি ll2 খালি থাকে, তারপর ll1 ফেরত দিন যদি data(ll1) <=data(ll2), তারপর new_head =ll1; next(new_head) =mergeList(next(ll1), ll2) অন্য নতুন_head =ll2; next(new_head) =mergeList(ll1, next(ll2)) রিটার্ন new_headEnd

split_list(start, ll1, ll2)

ইনপুট − লিঙ্ক করা তালিকার স্টার্ট পয়েন্টার, দুটি আউটপুট আর্গুমেন্ট ll1 এবং ll2

আউটপুট - লিঙ্ক করা তালিকা থেকে দুটি লিঙ্কযুক্ত তালিকা তৈরি করা হয়েছে

ধীরে শুরু করুন :=দ্রুত শুরু করুন :=পরবর্তী (শুরু করুন) দ্রুত শূন্য না হলে, দ্রুত করুন :=পরবর্তী (দ্রুত) যদি দ্রুত শূন্য না হয়, তাহলে ধীর :=পরবর্তী (ধীরে) দ্রুত :=পরবর্তী (দ্রুত) শেষ হওয়ার সময় ll1 :=শুরু ll2 :=পরবর্তী(ধীরে) পরবর্তী(ধীরে) :=nullEnd

একত্রিত করুন(শুরু)

ইনপুট - লিঙ্ক করা তালিকা

আউটপুট − বাছাই করা লিঙ্ক তালিকা

শুরু করুন মাথা =শুরু করুন যদি হেড নাল হয় বা পরের(হেড) নাল হয়, তারপর ফিরে আসুন split_list(head, ll1, ll2) mergeSort(ll1) mergeSort(ll2) start :=mergeList(ll1, ll2)শেষ

সোর্স কোড (C++)

#includeনেমস্পেস ব্যবহার করে std;class node {//define node to store data and next address public:int data; node *next;};void display(class node* start) { node* p =start; // বর্তমান নোড হেড করার সময় সেট করা হয়েছে (p !=NULL) { //ট্র্যাভার্স যতক্ষণ না বর্তমান নোডটি NULL cout না হয় <
 ডেটা <<" "; p =p -> পরবর্তী; // পরবর্তী নোডে যান }}নোড* getNode(int d) { node* temp =new node; temp -> ডেটা =d; temp -> next =NULL; রিটার্ন temp;}নোড* মার্জলিস্ট(নোড* ll1, নোড* ll2) { // দুটি সাজানো তালিকা নোড মার্জ করার জন্য ফাংশন* newhead =NULL; if(ll1 ==NULL) রিটার্ন ll2; if(ll2 ==NULL) রিটার্ন ll1; //পুনরাবৃত্তভাবে তালিকাগুলি মার্জ করুন যদি(ll1 -> ডেটা <=ll2 -> ডেটা) { newhead =ll1; newhead -> next =mergeList(ll1->next,ll2); } অন্য { newhead =ll2; newhead -> next =mergeList(ll1,ll2->পরবর্তী); } return newhead;}void splitList(node* start, node** ll1,node** ll2) { // flyod's tortoise algorithm node* slow =start; নোড* দ্রুত =শুরু -> পরবর্তী; while(fast!=NULL) { fast =fast -> next; if(fast!=NULL) { slow =slow -> next; fast =দ্রুত -> পরবর্তী; } } *ll1 =শুরু; *ll2 =ধীর -> পরবর্তী; // স্প্লিটিং স্লো -> next =NULL;} void mergeSort(node** start) { node* head =*start; নোড*ll1,*ll2; //বেস কেস if(head ==NULL || head->next ==NULL) { রিটার্ন; } স্প্লিটলিস্ট(হেড,&ll1,&ll2); // তালিকাটিকে দুটি ভাগে ভাগ করুন // বাম এবং ডান সাবলিস্ট একত্রিত করুন (&ll1); মার্জসোর্ট(&ll2); // দুই সাজানো তালিকা মার্জ করুন *start =mergeList(ll1,ll2); return;}int main() { cout <<"লিঙ্ক করা তালিকা তৈরি করা হচ্ছে:" <> k; node* head =getNode(k); //buliding তালিকা, প্রথম নোড cin>> k; temp =মাথা; while(k) { curr =getNode(k); temp -> next =curr;// প্রতিটি নোড temp =temp -> পরবর্তী; cin>> k; } cout<<"বাছাই করার আগে:" < 
আউটপুট
 
লিঙ্ক করা তালিকা তৈরি করা:তালিকা তৈরি করা বন্ধ করতে 0 লিখুন, অন্যথায় যেকোন পূর্ণসংখ্যা লিখুন8954156474981024260বাছাই করার আগে:89 54 15 64 74 98 10 24 26 বাছাই করার পরে:10 15 247 24968>