সি-তে মার্জ সর্টের সবচেয়ে খারাপ কেস সৃষ্টি করে এমন একটি পারমুটেশন খুঁজুন

ধারণা

উপাদানগুলির একটি প্রদত্ত সেটের ক্ষেত্রে, নির্ধারণ করুন যে এই উপাদানগুলির কোন স্থানান্তরের ফলে মার্জ সাজানোর সবচেয়ে খারাপ ক্ষেত্রে পরিণত হবে?

আমরা জানি, লক্ষণীয়ভাবে, মার্জ সর্ট সর্বদা O(n log n) সময় ব্যয় করে, তবে যে ক্ষেত্রে আরও তুলনার প্রয়োজন হয় সেগুলি সাধারণত অনুশীলনে আরও বেশি সময় ব্যয় করে। এখন আমাদের মূলত ইনপুট উপাদানগুলির একটি স্থানান্তর নির্ধারণ করতে হবে যা একটি সাধারণ মার্জ সর্ট অ্যালগরিদম প্রয়োগ করার সময় বাছাই করার সময় সর্বাধিক সংখ্যক তুলনার দিকে পরিচালিত করবে৷

উদাহরণ

নীচের উপাদানগুলির সেটটিকে সাজানো অ্যারে হিসাবে বিবেচনা করুন 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

ফলাফলপ্রাপ্ত ইনপুট অ্যারে যা মার্জ সাজানোর সবচেয়ে খারাপ ক্ষেত্রে পরিণত হবে তা হল 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26

পদ্ধতি

আমরা পরীক্ষা করি কিভাবে একটি ইনপুট সেটের জন্য মার্জ সাজানোর জন্য সবচেয়ে খারাপ কেস ইনপুট পেতে হয়?

এখন আমরা নিচের আপ পদ্ধতিতে অ্যারে তৈরি করার চেষ্টা করি

এখন সাজানো অ্যারেটি হতে দিন {11, 12, 13, 14, 15, 16, 17, 18}৷

এখন মার্জ সাজানোর সবচেয়ে খারাপ কেস তৈরি করার জন্য, উপরে সাজানো অ্যারের ফলে যে মার্জ অপারেশন হয়েছে তার সবচেয়ে বড় তুলনা হওয়া উচিত। এর ফলস্বরূপ, মার্জ অপারেশনে জড়িত বাম এবং ডান সাব-অ্যারেকে সাজানোর বিকল্প উপাদানগুলি সংরক্ষণ করা উচিত যেমন, বাম সাব-অ্যারে হওয়া উচিত {11, 13, 15, 17} এবং ডান সাব-অ্যারে হওয়া উচিত {12, 14 , 16, 18}। সুতরাং অ্যারের প্রতিটি উপাদান সর্বনিম্ন একবার তুলনা করা হবে এবং এর ফলে সর্বাধিক তুলনা হবে। এখন আমরা বাম এবং ডান সাব-অ্যারের জন্য একই যুক্তি প্রয়োগ করি। অ্যারের ক্ষেত্রে {11, 13, 15, 17}, সবচেয়ে খারাপ অবস্থা হবে যখন এর বাম এবং ডান সাব-অ্যারে যথাক্রমে{11, 15} এবং {13, 17} এবং অ্যারের জন্য {12, 14, 16, 18} সবচেয়ে খারাপ ঘটনা ঘটবে {12, 14} এবং {16, 18} এর জন্য৷

সম্পূর্ণ অ্যালগরিদম

WorstCase(arr[]) তৈরি করুন

• এখন আমরা বাম এবং ডানে দুটি অক্সিলারি অ্যারে তৈরি করি এবং তাদের মধ্যে বিকল্প অ্যারে উপাদান সংরক্ষণ করি৷

• আমরা বাম সাবয়ারের জন্য GenerateWorstCase বলি − GenerateWorstCase (বাম)

• আমরা ডান সাবয়ারের জন্য GenerateWorstCase বলি GenerateWorstCase (ডানে)

• এখন আমরা মূল অ্যারেতে বাম এবং ডান সাবয়ারের সমস্ত উপাদান কপি করি৷

উদাহরণ

// মার্জ সর্টের সবচেয়ে খারাপ কেস তৈরি করতে সি প্রোগ্রাম#include #include // একটি অ্যারেভয়েড প্রিন্ট অ্যারে(int A1[], int size1){ এর জন্য প্রিন্ট করার ফাংশন নির্দেশ করে i =0; i  
আউটপুট
 
সর্ট করা অ্যারে is11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ইনপুট অ্যারে যা মার্জ সাজানোর সবচেয়ে খারাপ ক্ষেত্রে পরিণত হবে is11 19 15 23 13 21 16224 16224>