মার্জ সর্ট হল খুবই কার্যকরী একটি সর্টিং অ্যালগরিদম।এটা Divide and Conquer পদ্ধতিতে কাজ করে। মানে ইনপুট অ্যারে টাকে কতগুলো ক্ষুদ্র ক্ষুদ্র সাব-প্রবলেমে ভাগ করে ফেলে,তারপর সেই ক্ষুদ্র ক্ষুদ্র অংশ গুলো কে মার্জ করে যে সমাধাণ গুলো পায়,সেগুলো একত্রিত করে মূল সর্টেড অ্যারে প্রডিউস করে।
ধর,নিচের অ্যারে টাকেই সর্ট করতে হবে।
এখন এই অ্যারে টাকে আমরা Left এবং Right নামে সমান দুই ভাগে ভাগ করব।
এখন Left[] এবং Right[] সাব-অ্যারে দুটি কে সর্ট করলে নিচের মত পাব।
→প্রাথমিক অবস্থায় Left[] এবং Right[] এর মধ্যকার Smallest Unpicked Number হল যথাক্রমে 10 এবং 13।এদের মধ্যে 10 ছোট হওয়ায় 10 চলে যাবে মূল সর্টেড অ্যারে তে।অতএব,এই ধাপের পর,
Unpicked Left[]={12,20,27}
Unpicked Right[]={13,15,22,25}
Produced Sorted Array[]={10}
→এরপর Left[] এবং Right[] এর মধ্যকার Smallest Unpicked Number হল যথাক্রমে 12 এবং 13। এদের মধ্যে 12 ছোট হওয়ায় 12 চলে যাবে মূল সর্টেড অ্যারে তে।অতএব,এই ধাপের পর,
Unpicked Left[]={20,27}
Unpicked Right[]={13,15,22,25}
Produced Sorted Array[]={10,12}
→এরপর Left[] এবং Right[] এর মধ্যকার Smallest Unpicked Number হল যথাক্রমে 20 এবং 13। এদের মধ্যে 13 ছোট হওয়ায় 13 চলে যাবে মূল সর্টেড অ্যারে তে।অতএব,এই ধাপের পর,
Unpicked Left[]={20,27}
Unpicked Right[]={15,22,25}
Produced Sorted Array[]={10,12,13}
→এরপর Left[] এবং Right[] এর মধ্যকার Smallest Unpicked Number হল যথাক্রমে 20 এবং 15। এদের মধ্যে 15 ছোট হওয়ায় 15 চলে যাবে মূল সর্টেড অ্যারে তে।অতএব,এই ধাপের পর,
Unpicked Left[]={20,27}
Unpicked Right[]={22,25}
Produced Sorted Array[]={10,12,13,15}
→এরপর Left[] এবং Right[] এর মধ্যকার Smallest Unpicked Number হল যথাক্রমে 20 এবং 22। এদের মধ্যে 20 ছোট হওয়ায় 20 চলে যাবে মূল সর্টেড অ্যারে তে।অতএব,এই ধাপের পর,
Unpicked Left[]={27}
Unpicked Right[]={22,25}
Produced Sorted Array[]={10,12,13,15,20}
→এরপর Left[] এবং Right[] এর মধ্যকার Smallest Unpicked Number হল যথাক্রমে 27 এবং 22। এদের মধ্যে 22 ছোট হওয়ায় 22 চলে যাবে মূল সর্টেড অ্যারে তে।অতএব,এই ধাপের পর,
Unpicked Left[]={27}
Unpicked Right[]={25}
Produced Sorted Array[]={10,12,13,15,20,22}
→এরপর Left[] এবং Right[] এর মধ্যকার Smallest Unpicked Number হল যথাক্রমে 27 এবং 25। এদের মধ্যে 25 ছোট হওয়ায় 25 চলে যাবে মূল সর্টেড অ্যারে তে। অতএব,এই ধাপের পর,
Unpicked Left[]={27}
Unpicked Right[]={}
Produced Sorted Array[]={10,12,13,15,20,22,25}
→ এরপর Left[] সাব-অ্যারে তে শুধু 27 আছে,সেটা চলে যাবে মূল সর্টেড অ্যারে তে।অতএব,এই ধাপের পর,
Unpicked Left[]={}
Unpicked Right[]={}
Produced Sorted Array[]={10,12,13,15,20,22,25,27}
আমরা এখন দুটি সর্টেড সাব-অ্যারে কে মার্জ করে মেইন সর্টেড অ্যারে প্রডিউস করতে পারি। এতক্ষন যে প্রসেস গুলো করলাম,সেটার স্যাম্পল কোড টা দেখি,
উপরে প্রসেস গুলো যেভাবে বলা হয়েছে কোডিং টাও ঐরকমই। প্রথম while লুপে আমরা Left[] এবং Right[] এর মধ্যকার Smallest Unpicked Number টা নিয়ে মেইন সর্টেড অ্যারে তে রেখে দিচ্ছি।Smallest Unpicked Number গুলো নিতে নিতে Left[] এবং Right[] এর মধ্যকার কোন একটা সাব- অ্যারে আগে Empty হয়ে যাবে।তখন অন্য সাব- অ্যারে তে যে Unpicked Number গুলো থেকে যাবে সেগুলো মেইন সর্টেড অ্যারে তে নেয়ার জন্য পরের দুইটা while লুপের যে কোন একটা প্রসেস হবে।
খেলা তো শুরু এখন!🙈
এতক্ষন পর্যন্ত আমরা যা জানি,তাতে কেউ আমাদের দুটি সাব-অ্যারে সর্ট করে দিলে সেগুলো কে মার্জ করে আমরা মেইন অ্যারে টা সর্ট করতে পারব।কিন্তু এই 'কেউ' টা কে?😕'কেউ' টা আসলে কেউই না,আমরাকেই সর্ট করতে হবে😅। কিভাবে?😢 রিকার্শন সম্পর্কে একটু আধটু ধারণা থাকলেও এতক্ষ্ণ বুঝে যাবার কথা।আর রিকার্শন কি তা জানতে হলে ফাহিম এবং যোবায়ের ভাইয়ার এই লেখা দুটি অবশ্যই পড়ে নিতে হবে।না পড়লে পাপ হবে,পাপ😑।
যাক,ভয়ের কিছু নেই, আমরাও সর্ট করব না😃সর্ট করায়ে নিব😏। আমরা একটা ফাংশন কে রিকার্শিভ্লি কল করতে থাকব।যেটা আমাদের কে কোন একটা অ্যারে কে Left[] এবং Right[] এই দুই ভাগে ভাগ করে দিবে।এভাবে প্রতিটা Left[] এবং Right[] কে রিকার্শিভলি কল করে স্প্লিট করতেই থাকব, স্প্লিট করতে করতে যখন সাব অ্যারের লেন্থ ২ এর কম হবে তখন ফাংশন হাপায়ে গিয়ে বলবে "আমি আর পারছি না"😝 অর্থাৎ ফাংশন রিটার্ন করবে😁। নিচের ছবিটা দেখা যাক,
ছবিঃসংগৃহীত
উপরের ছবিতে আমরা দেখতে পাচ্ছি যে,একটা অ্যারে কে স্প্লিট করতে করতে যখন তার লেন্থ ১ হয়ে যাচ্ছে তখন ফাংশন সিম্পলি রিটার্ন করছে এবং Merge() ফাংশন কে কল করে মার্জ করা শুরু করছে। কোড দেখে আমরা আরো ভাল ভাবে বুঝার চেষ্টা করবঃ
এখন MergeSort(int arr[],int n) ফাংশন টা কল করলে।প্রথমে অ্যারে টাকে Left[]={27,10,12,20} এবং Right[]={25,13.15,22} নামে সমান দুভাগে ভাগ ফেলবে। এরপর যেহেতু Merge(Left,nL) আগে আছে তাই, Left[] তার বন্ধু Right[] কে বলবে,তুই একটু ওয়েট কর।আমি কাজ টা সেরে নেই।Right[] এর আর কি করার বন্ধু বলসে,চুপচাপ বসে আছে।এই সময়ে Left[]={27,10,12,20} আবার MergeSort(int arr[],int n) ফাংশনের মধ্যে ঢুকে গিয়ে নিজে আবার Left[]={27,10} এবং Right[]={12,20} এ ভাগ হয়ে গেছে।আগের মতই এখানেও Right[]={12,20} চুপচাপ বসে আছে।এই সময়ে Left[]={27,10} আবার MergeSort(int arr[],int n) ফাংশনে ঢুকে Left[]={27} এবং Right[]={10} ভাগে হয়ে গেছে। এখানেও যথারীতি Right[]={10} চুপচাপ বসে আছে এবং এই সময়ে Left[]={27} আবার MergeSort(int arr[],int n) ফাংশনে ঢুকে গেছে।এইবার তো MergeSort(int arr[],int n) এর একঘেয়েমি এসে গেছে,বলে ভাই তুই আর আসিস না,ফেরত যা। অর্থাৎ লেন্থ ১ হয়ে যাওয়ায় ফাংশন রিটার্ন করবে।
এখন MergeSort(Right,nR) ফাংশন টা কল হবে,এখন যেহেতু আমাদের Right[]={10} অর্থাৎ লেন্থ ১ তাই MergeSort(Right,nR) এক্ষত্রে রিটার্ন করবে। যেহেতু প্রথম দুই ফাংশন রিটার্ন হয়ে গেছে,এখন Merge(Left,Right,nL,nR) ফাংশন টা কল হবে এবং এখন Left[]={27} এবং Right[]={10} কে মার্জ করে {10,27} বানায়ে আগের স্টেপে পাঠাবে।এখন ঐ স্টেপে Right[]={12,20} যেহুতু তখন চুপচাপ বসে ছিল,এখন সে এক্সিকিউট হবে। সে নিয়মানুযায়ী এক্সিকিউট হয়ে {12,20} হবে(কোন চেঞ্জ হবে না,যেহেতু তারা আগে থেকেই সর্টেড)।
এখন মার্জ হওয়া {10,27} এবং {12,20} সাব- অ্যারে দুটি আবার মার্জড হয়ে {10,12,20,27} হবে এবং আগের স্টেপে চলে যাবে। যেখানে Right[]={25,13.15,22} চুপচাপ বসে ছিল।তাই এখন সে এক্সিকিউট হবে। এবং যথারীতি ফাংশন গুলি রিকার্শিভ্লি কল হয়ে, {13.15,22,25,} এই রকম একটা সাব- অ্যারে তে পরিণত হবে।এখন মার্জড হওয়া {10,12,20,27} এবং {13.15,22,25,} পুনরায় মার্জড হয়ে {10,12,13,15,20,22,27} এ পরিণত হয়ে সর্ট হয়ে যাবে সর্ট হয়ে যাবে!
সম্পূর্ণ কোড টা নিচের লিংকে পাওয়া যাবে,
সম্পূর্ণ কোডঃ https://ideone.com/cRUZK4
কমপ্লেক্সিটিঃ
⇾Best Case: O(N log N)
⇾Average Case: O(N log N)
⇾Worst Case: O(N log N)
কমপ্লেক্সিটিঃ
⇾Best Case: O(N log N)
⇾Average Case: O(N log N)
⇾Worst Case: O(N log N)
No comments:
Post a Comment