সর্টিং অ্যালগোরিদম - Sorting algorithm

সর্টিং: মার্জ সর্ট (Merge Sort) অ্যালগরিদম

Merge sort Bengali tutorial/ Merge sort Bangla tutorial

মার্জ সর্ট (Merge sort) একটি গুরুত্বপূর্ণ সর্টিং অ্যালগরিদম (Sorting algorithm) যা O(n \log{n}) টাইম কম‌প্লে‌ক্সি‌টি‌তে একটি অ্যারেকে সর্ট করতে পারে। এটি একটি ভাগ করো শাসন করো বা Divide and conquer অ্যালগরিদম যেখানে রিকার্শনের মাধমে একটি অ্যারেকে প্র‌তিবা‌রে দুইভাগে বিভক্ত করে আলদা আলাদা করে সর্ট করা হয়। তারপর অংশগুলোকে মার্জ করলে একটি সর্টেড অ্যারে পাওয়া যায়। [Merge sort Bangla tutorial]

মার্জ সর্ট কিভাবে কাজ করে?

আগেই বলেছি মার্জ সর্ট একটি ভাগ করো শাসন করো বা Divide and conquer অ্যালগরিদম। এটি কিভাবে কাজ করে একটু বুঝার চেস্টা করি।

ধরা যাক আপনাকে দায়িত্ব দেয়া হলো ১০ টি সংখ্যাকে ছোট থেকে বড় আকারে সাজিয়ে দিতে। আপনি এই কাজটি আপনার দুইজন বন্ধু A এবং B কে ভাগ করে দিলেন, A কে বললেন তুই আমাকে 0 থেকে 4 ইনডেক্স পর্যন্ত সর্ট করে দে, আর B কে বললেন তুই আমাকে 5 থেকে 9 পর্যন্ত ইনডেক্স সর্ট করে দে।

এখানে l হলো বাম দিকের ইনডেক্স এবং r হলো ডান দিকের ইনডেক্স। ইনডেক্সিং শুন্য ভিত্তিক এবং মাঝের বিন্দুর মান \frac{l+r}{2} এর সূত্র দিয়ে বের করা হয়েছে।

iishanto.com
Divide and conquer

এখন A এর C এবং D নামে দুইজন বন্ধু আছে ধরি। A, C কে বলল দোস্ত আমাকে তুই l=0 থেকে r=2 পর্যন্ত সর্ট করে দে। D কে বলল তুই আমাকে l=3 থেকে r=4 পর্যন্ত সর্ট করে দে। এভাবে C এবং D তাদের বন্ধুদের ভাগ করে দিতে থাকলো। একসময় দেখা যাবে অ্যারের সাইজ ১ হয়ে গেছে। তখন কিন্তু অ্যারেটা সর্টেড। কারন ১ উপাদান আছে বিশিষ্ট অ্যারে সবসময় সর্টেড। নিচের চিত্রে H এর কাজ এখানেই শেষ। কিন্তু G আবার দুইভাগ করে নতুন দুইজন কে সর্ট করে দিতে বলবে।

Merge sort divide

এভাবে ভাগ করতে করতে যখন আমরা বেস কেসে (Base case) বা অ্যারের সাইজ ১ এই অবস্থায় যাবো আমরা রিটার্ন দেয়া শুরু করবো।

ধরি A এর বন্ধু C এবং D তাদের দেয়া অ্যারেটি সর্ট করে ফেলেছে। এখন C এবং D তাদের অংশকে বন্ধু A এর কাছে দিবে, যেহেতু A তাদের এই কাজটি দিয়েছিলো। এখন A এর কাজটি হলো সর্টেড অ্যারে দুটিকে মার্জ করা (Merge করার কাজটি C এবং D কেও করতে হয়েছিলো, কারন তারাও তাদের বন্ধুদের ভাগ করে দিয়েছিলো তাদের কাজটি) এবং তাকে আপনার কাছে রিটার্ন করা।

Source: internet

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

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

Merge sort Bangla Tutorial

ভাগ করো শাসন করো পদ্ধতিটি কোড করার জন্য আমাদেরকে রিকার্শন (Recursion) ব্যবহার করতে হবে। তাই আগে থেকে আপনাদের রিকার্শন নিয়ে ধারনা থাকা লাগবে।

আমরা mergeSort নামে একটি ফাংশন তৈরি করবো। এই ফাংশনটি তিনটি প্যারামিটার নিবে। প্রথমটি আমাদের মূল অ্যারে arr[]। দ্বিতীয় এবং তৃতীয়টি হলো l এবং r, বাম ইনডেক্স এবং ডান ইনডেক্স সুতরাং ফাংশনের প্রোটোটাইপ হলো,

Merge sort C++ implementation

এখানে প্রথমেই বলে রাখি, আমরা কেন void রিটার্ন করেছি। যেহেতু C এবং C++ এ ফাংশনের প্যারামিটার গুলোতে অ্যারে Reference হিসেবে পাস হয়। তাই আমাদের কিছু রিটার্ন করতে হবে। merge ফাংশনে যখন l এবং r রেঞ্জে মার্জ করা হবে তখন সব কিছু সর্টেড আকারে আপডেট হয়ে যাবে।

২ নং লাইনে আমরা বেস কেস লিখেছি। যখন l>r বা l, r এর থেকে বড় হবে তখন আমরা আর প্রসেস করবো না। কারন বাম ইন্ডেক্স ডান ইন্ডেক্স থেকে বড় হতে পারে না।

যদি l==r হয় তবে আমরা বলতে পারি বর্তমান রেঞ্জে একটিই উপাদান আছে। তাই তখনও আমরা আর প্রসেস করবো না। রিটার্ন করে দিবো। ২ নং লাইনে এই দুটি শর্তই পরিক্ষা করা হয়েছে।

৪ নং লাইনে আমরা অ্যারেকে দুইভাগে ভাগ করার জন্য মাঝের ইনডেক্স হিসাব করেছি। তার পরের লাইনে আমরা একটি রিকার্সিভ কল করেছি। রিকার্সিভ কলটিকে যদি আমি অনুবাদ করি এমন দারায়,

অ্যারে arr[] কে l এবং mid রেঞ্জের মধ্যে সর্ট করে দাও। পরবর্তী লাইনেও আমরা mid+1 থেকে r এর রাঞ্জে একটি রিকার্সিভ কল করেছি। এভাবে রিকার্সিভ কল হতে থাকবে যতক্ষণ না পর্যন্ত আমরা বেস কেসে পৌছাই।

রিকার্সিভ কল শেষ হবার পর আমরা ৮ নং লাইনে আমরা রেঞ্জ l থেকে mid এবং mid+1 থেকে r কে যাদের রিকার্সিভ কলের মাধমে সর্ট করা হয়েছিলো তাদের মার্জ করবো। তারপর রিটার্ন করবো। এই হলো কোড।

দুটি সর্টেড অ্যারেকে মার্জ করা

মার্জ সর্টের একটি গুরুত্বপূর্ণ অংশ হলো দুইটি সর্টেড অ্যারেকে মার্জ করা। এই ধাপে আমরা দেখবো কিভাবে দুইটি সর্টেড অ্যারেকে মার্জ করা যায়। প্রক্রিয়াটি বুঝার জন্য আমরা নিচের আনিমেশনটি দেখবো।

উপরের এনিমেশনের মতো করেই আমরা দুইটি অ্যারের একটি একটি করে উপাদান নিয়ে তুলনা করবো। যখন যেটা ছোট হবে তাকে মূল অ্যারেতে রাখবো। সবশেষে যদি কোন অ্যারের উপাদান বেশি হয় তা রেখে দিবো। এর কোডটি ভালো করে লক্ষ করলেই বুঝবেন ইনশাল্লাহ।

আমাদেরকে প্রথমে l থেকে mid এবং mid+1 থেকে r পর্যন্ত আলাদা করে নিতে হবে। আমরা arr[] এর l থেকে r রেঞ্জের উপাদান গুলোকে A[] এবং B[] অ্যারেতে কপি করার কাজ টুকু করেছি 13 থেকে 20 নং লাইনের দুইটি লুপের মাধ্যমে। A এর সাইজ n এবং B এর সাইজ m যা 4 এবং 5 নং লাইনের মাধ্যমে বের করা হয়েছে। যেহেতু merge ফাংশন কল করার সময় l – mid আর mid+1 – r আলদা আলাদা করে সর্টেড ছিলো তাই আমাদের A[] এবং B[] ও সর্টেড হবে

এর পর ২৪ থেকে ৩১ নং লাইনে আমরা দুইটি সর্টেড অ্যারে A[] এবং B[] কে মূল অ্যারেতে সর্টেড আকারে মার্জ করেছি। এই লুপে কি হচ্ছে বুঝার আর খাতা কলমে ভিজুয়ালাইজ করুন।

তারপর ৩৮ থেকে ৪৭ নং লাইনে আমরা A এবং B অ্যারের বাড়তি উপাদান (যদি থাকে) তাদের মূল অ্যারেতে রেখেছি।

যাইহোক
Source: me.me

Merge sort Bangla tutorial: full code in C++

Merge sort Bengali tutorial: Algorithm analysis

মার্জ সর্ট (Merge sort) যেহেতু প্রতিবারে একটি অ্যারেকে দুটি ভাগে বিভক্ত করছে তাই এর টাইম কমপ্লেক্সিটি দাড়ায় O(\log{n}) । আবার প্রতি ধাপে মার্জ করা লেগেছে যার মোট কমপ্লেক্সিটি O(n) । তাই মার্জ সর্টের Best case এবং Worst case উভয় টাইম কমপ্লেক্সিটি O(n \log{n})

মার্জ সর্টের স্পেস কমপ্লেক্সিটি O(n)

এই হলো আমাদের মার্জ সর্টের গল্প। আগামীতে কোন গল্প লিখা যায় ভাবতে থাকি। পরীক্ষা হতে পারে। পাশ করতে হবে মাথাতে এটাই ঘুরতেছে। EEE কোর্সের ওহম এর সূত্র বাদে কিছুই মনে করতে পারছি না। তাই আপাতত বিদায়। দোয়া করবেন।

লেখাটি কেমন লেগেছে আপনার?

রেটিং দিতে হার্টের উপর ক্লিক করুন।

গড় রেটিং / 5. মোট ভোট:

আপনি প্রথম ভোটদাতা.

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button