Delower's Programming Diary: মার্জ সর্ট

ধর,তোমরা কয়েক জন বন্ধু দার্জিলিং ঘুরতে গিয়ে ক্যাটরিনার দেখা পাইলা।কিন্তু তোমাদের সবাই ক্যাট কে চায়ই চায়।ক্যাট ও তোমাদের সবাই কে চায়💚 কারণ তোমরা সবাই অনেক স্মার্ট😂।কিন্তু ক্যাট ভাবল সবাইকে নিলে, ব্যাপারটা কেমন অনৈতিক হয়ে যায়💘 তাই সে তোমাদের একটা প্রস্তাব দিল,কত গুলো নাম্বার কে যে যত কম টাইম কমপ্লেক্সিটি তে সর্ট করতে পারবে,তাকেই সে বফ বানাবে😙। তো তুমি চিন্তা করলে,বাবল সর্ট করলে নিশ্চিত ধরা খাব,তার চেয়ে বরং মার্জ সর্ট মেরে দেয়(কারণ তুমি ল্যাব ভাইভার জন্য মুখস্ত করছিলা🙌 যে মার্জ সর্টের কমপ্লেক্সিটি(worst case: O(N log N)),অন্ততপক্ষে বাবল সর্টের(worst case: O(N^2)) চেয়ে কম)।দেখা যাক,কপালে কি আছে!😰কিন্তু তুমি তো মার্জ সর্টও জানো না।তাইলে চলো শিখে নেই,ক্যাট কে পাবার জন্য হলেও!😍

মার্জ সর্ট হল খুবই কার্যকরী একটি সর্টিং অ্যালগরিদম।এটা Divide and Conquer পদ্ধতিতে কাজ করে। মানে ইনপুট অ্যারে টাকে কতগুলো ক্ষুদ্র ক্ষুদ্র সাব-প্রবলেমে ভাগ করে ফেলে,তারপর সেই ক্ষুদ্র ক্ষুদ্র অংশ গুলো কে মার্জ করে যে সমাধাণ গুলো পায়,সেগুলো একত্রিত করে মূল সর্টেড অ্যারে প্রডিউস করে।

ধর,নিচের অ্যারে টাকেই সর্ট করতে হবে।

এখন এই অ্যারে টাকে আমরা Left এবং Right নামে সমান দুই ভাগে ভাগ করব।

এখন কেউ যদি কোনভাবে আমাদের কে এই Left[] এবং Right[] সাব-অ্যারে দুটি সর্ট করে দেয় তাহলে কিভাবে আমরা এই দুটি সর্টেড সাব-অ্যারে কে মার্জ করে মূল অ্যারে কে সর্ট করতে পারি,সেটাই আগে দেখব।ঐ সাব-অ্যারে দুটি কিভাবে সর্ট করব সেটা এখন ভাবনার বিষয় না।আপাততঃ ধরে নাও কোন এক অলৌকিক শক্তি দিয়ে আমরা সেটা করতে পারব😎।

এখন Left[] এবং Right[] সাব-অ্যারে দুটি কে সর্ট করলে নিচের মত পাব।

এখন এই দুটি সর্টেড সাব-অ্যারে কে মার্জ করলেই আমরা মূল সর্টেড অ্যারে পেয়ে যাব। মার্জ করার সময় আমরা সবসময় Left[] এবং Right[] সাব-অ্যারে দুটির মধ্যকার Smallest Unpicked Number টা নিব।

→প্রাথমিক অবস্থায় 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}

আমরা এখন দুটি সর্টেড সাব-অ্যারে কে মার্জ করে মেইন সর্টেড অ্যারে প্রডিউস করতে পারি। এতক্ষন যে প্রসেস গুলো করলাম,সেটার স্যাম্পল কোড টা দেখি,

	void Merge(int Left[],int Right[],int arr[],int nL,int nR){
	int i=0,j=0,k=0;

	while(i<nL && j<nR){
	if(Left[i]<=Right[j]){
	arr[k++]=Left[i++];
	}
	else{
	arr[k++]=Right[j++];
	}
	}

	while(i<nL){
	arr[k++]=Left[i++];
	}

	while(j<nR){
	arr[k++]=Right[j++];
	}
	}

view raw Merge.cpp hosted with ❤ by GitHub

উপরে প্রসেস গুলো যেভাবে বলা হয়েছে কোডিং টাও ঐরকমই। প্রথম while লুপে আমরা Left[] এবং Right[] এর মধ্যকার Smallest Unpicked Number টা নিয়ে মেইন সর্টেড অ্যারে তে রেখে দিচ্ছি।Smallest Unpicked Number গুলো নিতে নিতে Left[] এবং Right[] এর মধ্যকার কোন একটা সাব- অ্যারে আগে Empty হয়ে যাবে।তখন অন্য সাব- অ্যারে তে যে Unpicked Number গুলো থেকে যাবে সেগুলো মেইন সর্টেড অ্যারে তে নেয়ার জন্য পরের দুইটা while লুপের যে কোন একটা প্রসেস হবে।

খেলা তো শুরু এখন!🙈
এতক্ষন পর্যন্ত আমরা যা জানি,তাতে কেউ আমাদের দুটি সাব-অ্যারে সর্ট করে দিলে সেগুলো কে মার্জ করে আমরা মেইন অ্যারে টা সর্ট করতে পারব।কিন্তু এই 'কেউ' টা কে?😕'কেউ' টা আসলে কেউই না,আমরাকেই সর্ট করতে হবে😅। কিভাবে?😢 রিকার্শন সম্পর্কে একটু আধটু ধারণা থাকলেও এতক্ষ্ণ বুঝে যাবার কথা।আর রিকার্শন কি তা জানতে হলে ফাহিম এবং যোবায়ের ভাইয়ার এই লেখা দুটি অবশ্যই পড়ে নিতে হবে।না পড়লে পাপ হবে,পাপ😑।

যাক,ভয়ের কিছু নেই, আমরাও সর্ট করব না😃সর্ট করায়ে নিব😏। আমরা একটা ফাংশন কে রিকার্শিভ্লি কল করতে থাকব।যেটা আমাদের কে কোন একটা অ্যারে কে Left[] এবং Right[] এই দুই ভাগে ভাগ করে দিবে।এভাবে প্রতিটা Left[] এবং Right[] কে রিকার্শিভলি কল করে স্প্লিট করতেই থাকব, স্প্লিট করতে করতে যখন সাব অ্যারের লেন্থ ২ এর কম হবে তখন ফাংশন হাপায়ে গিয়ে বলবে "আমি আর পারছি না"😝 অর্থাৎ ফাংশন রিটার্ন করবে😁। নিচের ছবিটা দেখা যাক,

ছবিঃসংগৃহীত

উপরের ছবিতে আমরা দেখতে পাচ্ছি যে,একটা অ্যারে কে স্প্লিট করতে করতে যখন তার লেন্থ ১ হয়ে যাচ্ছে তখন ফাংশন সিম্পলি রিটার্ন করছে এবং Merge() ফাংশন কে কল করে মার্জ করা শুরু করছে। কোড দেখে আমরা আরো ভাল ভাবে বুঝার চেষ্টা করবঃ

	void MergeSort(int arr[],int n){
	if(n<2) return;
	int mid=n/2;
	int nL=mid;
	int nR=(n-mid);
	int Left[nL],Right[nR];
	for(int i=0;i<nL;i++) Left[i]=arr[i];
	for(int i=nL;i<n;i++) Right[i-mid]=arr[i];

	MergeSort(Left,nL);
	MergeSort(Right,nR);
	Merge(Left,Right,arr,nL,nR);
	}

view raw MergeSort.cpp hosted with ❤ by GitHub

এখন 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)