মার্জ সর্ট , সর্ট করার খুবই কার্যকর একটি অ্যালগোরিদম । এটি একটি Divide and Conquer অ্যালগোরিদম । তার আগে আমরা জেনে নিই Divide and Conquer অ্যালগোরিদম জিনিসটা কি ?
Divide and Conquer অ্যালগোরিদম , রিকার্সিভলি একটি সমস্যাকে একই ধরনের দুই বা ততোধিক ক্ষুদ্র ক্ষুদ্র সমস্যায় ভাগ করে এবং ভাগ করা প্রতিটি ক্ষুদ্র সমস্যাকে সমাধান করে একত্রিত করে মূল সমস্যাটির সমাধান করে ।
অর্থাৎ এই অ্যালগোরিদমের তিনটি অংশ রয়েছে ঃ
এখন মূল আলোচনায় আসা যাক । ধরা যাক , আমাদের কাছে একটা অ্যারে আছে এবং এর মানগুলো হল : 27,10,12,20,25,13,15,22 ।
অ্যারের মানগুলোকে আমরা ছোট থেকে বড় আকারে সাজাতে চাই ।
তার আগে আমরা নিচের ছবির দিকে একটু লক্ষ্য করি ঃ
উপরের ছবির দিকে মনোযোগ সহকারে লক্ষ্য করলে আমরা দেখবো যে, অ্যারেকে রিকার্সিভলি দুই ভাগে ভাগ করা হচ্ছে যতক্ষণ পর্যন্ত না এর সাইজ ১ হয় । সাইজ ১ হয়ে গেলে এবার মার্জ করার পালা । এখন বাম ও ডানপাশের অ্যারেকে মার্জ করে ছোট থেকে বড় আকারে সাজানো হয় । এভাবে মার্জ করা বাম ও ডান পাশের অ্যারেকে আবার মার্জ করা হয় এবং যতক্ষণ পর্যন্ত না সর্টেড অর্ডার পাওয়া যায় ততক্ষণ পর্যন্ত এই প্রক্রিয়া চলতে থাকে ।
Code Implementation :
অনেক ক্ষেত্রে ডাটা গুলো সর্ট করতে মিনিমাম কয়টা ইনভার্সন(Inversion) লাগে সেটা জানতে চাওয়া হয় । এটা বের করার পদ্ধতি হল যখন আমরা মার্জ করব তখন ডানপাশের অ্যারের মানগুলো বামপাশের অ্যারের বাকি কতগুলো মান থেকে ছোট সেই সংখ্যা গননা করে হিসেব করলেই আমরা ইনভার্সন সংখ্যা পেয়ে যাবো ।
Complexity of Merge Sort :
Reference :
Divide and Conquer অ্যালগোরিদম , রিকার্সিভলি একটি সমস্যাকে একই ধরনের দুই বা ততোধিক ক্ষুদ্র ক্ষুদ্র সমস্যায় ভাগ করে এবং ভাগ করা প্রতিটি ক্ষুদ্র সমস্যাকে সমাধান করে একত্রিত করে মূল সমস্যাটির সমাধান করে ।
অর্থাৎ এই অ্যালগোরিদমের তিনটি অংশ রয়েছে ঃ
- Divide : একটি সমস্যাকে একই ধরনের দুই বা ততোধিক ক্ষুদ্র ক্ষুদ্র সমস্যায় ভাগ করে ।
- Conquer : রিকার্সিভলি সেই ক্ষুদ্র ক্ষুদ্র সমস্যার সমাধান করে ।
- Combine : ক্ষুদ্র ক্ষুদ্র সমস্যার সমাধানগুলো একত্রিত করে মূল সমস্যাটির সমাধান করে ।
এখন মূল আলোচনায় আসা যাক । ধরা যাক , আমাদের কাছে একটা অ্যারে আছে এবং এর মানগুলো হল : 27,10,12,20,25,13,15,22 ।
অ্যারের মানগুলোকে আমরা ছোট থেকে বড় আকারে সাজাতে চাই ।
তার আগে আমরা নিচের ছবির দিকে একটু লক্ষ্য করি ঃ
 |
| মার্জ সর্টের প্রক্রিয়া |
Code Implementation :
অনেক ক্ষেত্রে ডাটা গুলো সর্ট করতে মিনিমাম কয়টা ইনভার্সন(Inversion) লাগে সেটা জানতে চাওয়া হয় । এটা বের করার পদ্ধতি হল যখন আমরা মার্জ করব তখন ডানপাশের অ্যারের মানগুলো বামপাশের অ্যারের বাকি কতগুলো মান থেকে ছোট সেই সংখ্যা গননা করে হিসেব করলেই আমরা ইনভার্সন সংখ্যা পেয়ে যাবো ।
Complexity of Merge Sort :
- Best Case : O (N log N)
- Average Case : O(N log N)
- Worst Case : O(N log N)
সমাধানের জন্য কয়েকটা সমস্যা :
0 comments: (+add yours?)
Post a Comment