পোস্টটি পড়া হয়েছে 12,847 বার
মার্জ সর্ট অ্যালগরিদম - Merge Sort Algorithm

মার্জ সর্ট অ্যালগরিদম – Merge Sort Algorithm

Post updated on 20th September, 2019 at 11:33 pm

ধরো স্কুলের মাঠে ইয়া লম্বা দুইটা লাইন আছে। বাচ্চারা এই দুই লাইনে ছোট থেকে বড় আকারে দাঁড়িয়ে আছে। দুটি লাইনেরই একদম সামনের বাচ্চাটা সবচেয়ে খাটো আর লাইনের শেষের বাচ্চাটা সবচেয়ে লম্বা। তোমাকে বলা হল এই দুইটা লাইনের বাচ্চাদেরকে খাটো থেকে লম্বা এই অর্ডারে একটা লাইনে সাজাতে। তাহলে কী করবে?

স্বাভাবিক ভাবেই আমাদের মাথায় আসবে যে, যেহেতু দুইটা লাইনই আলাদা আলাদা ভাবে সাজানো অবস্থায় আছে। তাই যখন এক লাইন করতে হবে তখন লাইন দুইটার শুরুর দুইজনের হাইটের মধ্যে কম্পেয়ার করব। ধর প্রথম লাইনের হাইট ১, ৩, ৫, ৭, ৯ আর দ্বিতীয় লাইনের বাচ্চাদের হাইট ২, ৪, ৬, ৮, ১০। এখন দুটি লাইনকে একসাথে করার জন্য আমরা প্রথমে উভয় লাইনের থেকে একজন করে নিয়ে এসে মাপ দিব। প্রথম লাইন থেকে ১ আর দ্বিতীয় লাইন থেকে ২ কে নিয়ে আসব। দেখব ১ ছোট, তাই আমাদের নতুন লাইনের প্রথমে থাকবে ১। প্রথম লাইনের শুরুতে এখন আছে ৩। দ্বিতীয় লাইনের শুরুতে আছে ২। এরপর ৩ ও ২ এর মাঝে চেক করব কে ছোট? ২ যেহেতু ছোট তাই একে নতুন অ্যারেতে রেখে দিব। দুইটা লাইনের শুরুতে এখন কে কে আছে? প্রথমটায় ৩ ও দ্বিতীয়টায় ৪। এখন এদের মধ্যে আবার চেক করব কে ছোট? যে ছোট হবে তাকে নতুন লাইন ২ এর পরে রাখব। লাইন দুইটির বাচ্চাদের সংখ্যা যদি অসমান হয়? অর্থাৎ একটা লাইনে আছে ১০ জন আরেকটা লাইনে আছে ১৫ জন তখন কী করবে? ছোট লাইনে যত জন আছে তত পর্যন্ত দুই লাইনের বাচ্চাদের মধ্যে কম্পেয়ার হবে। যদি ১০ জন বাচ্চার লাইনের সবাই নতুন লাইনে ঢুকে পড়ে তাহলে ধরো আরেকটা লাইনে ৫ জন বাকি আছে। আর এই ৫ জনও কিন্তু নিজেদের মধ্যে সর্টেড হয়েই আছে। তাই এদেরকে সিরিয়াল্যি নতুন লাইনের পিছনে ঢুকিয়ে দিলেই কাজ শেষ! এভাবে আমরা O(n) কমপ্লেক্সিটিতে দুটি sorted array কে Merge করতে পারি।

এবার উপরের প্যারা দুটি ভুলে যাও। নতুন জিনিস চিন্তা করব এখন। ধরো আমাদের কাছে একটাই অ্যারে আছে। ৫, ৬, ৯, ২, ১, ৪, ৮, ১০, ৩, ৭। মানগুলো এলোমেলো। সর্ট করা লাগবে। উপরের নিয়মে আমরা কাজ করতে তখনই পারব যখন দুটি অ্যারে থাকবে যারা নিজেরা সর্টেড। কিন্তু আমাদের কাছে আছে একটা অ্যারে। তাহলে কী করা যায়?

আমরা একটা কাজ করি। এই অ্যারেটাকে দুই ভাগ করে ফেলি। অ্যারের ০ থেকে ৪ নাম্বার ইন্ডেক্স পর্যন্ত একটা ভাগ (৫, ৬, ৯, ২, ১) আর ৫ থেকে ৯ নাম্বার ইন্ডেক্স পর্যন্ত দ্বিতীয় ভাগ (৪, ৮, ১০, ৩, ৭)। একই অ্যারের মধ্যেই এই দুটি ভাগকে কল্পনা করো দুটি আলাদা অ্যারে হিসেবে। ডেসটিনির মত মনে করো আমার আন্ডারে একটা লেফট হ্যান্ড আছে আরেকটা রাইট হ্যান্ড আছে। ধরো তুমি আমার লেফট হ্যান্ড। তোমাকে দিলাম প্রথম অ্যারেকে সর্ট করার কাজ আর রাইট হ্যান্ডকে দিলাম দ্বিতীয় অ্যারে সর্ট করার কাজ। তোমাকে চাপাবাজি, গলাবাজি থেকে শুরু করে সব কিছু শিখায় দিছি আগের থেকেই। এখন তুমি কেমনে আমাকে সর্ট করে এনে দিবে আমি জানি না। তোমার কাজ হচ্ছে সর্ট করে দেয়া, সর্ট করে আমাকে ঐ(৫, ৬, ৯, ২, ১) অ্যারের ০ থেকে ৪ ইন্ডেক্স পর্যন্ত যেই ভ্যালুগুলা দিতে হবে তা হচ্ছে ১, ২, ৫, ৬, ৯। তুমি ০ থেকে ৪ ইন্ডেক্সকে সর্ট করে দিবা, আমার ডাইন হাত ৫ থেকে ৯ পর্যন্ত সর্ট করে দিবে। আমি এইসব সর্ট-মর্ট করতে পারব না। আমি জাস্ট তোমাদের থেকে পাওয়া সর্টের দুইটা অ্যারেকে পোস্টের প্রথম দুই প্যারার মত করে মার্জ করব। মজা না?

মার্জ সর্ট - Merge Sort
Merge Sort Visualization. Photo Credit: Wikipedia

তোমাকে (৫, ৬, ৯, ২, ১) এই অ্যারে দিছি সর্ট করতে। তুমি কি বসে যাবা বাবল সর্ট নিয়ে? মোট্টেও না! তাইলে আর ডাইন হাত, বাম হাতের খেলা থাকলো মিয়া? তোমারে সর্ট করা শিখাইছি, সাথে এইটাও শিখাইছি যে কেমনে তোমার হাতে থাকা অ্যারেটা তোমার নিচে যারা ডাইন-বাম আছে তাদেরকে দিয়া করাইতে হবে। তুমি কী করলা? তুমি তোমার বাম হাত বজলুকে দিলা (৫, ৬, ৯) কে সর্ট করে দেয়ার জন্য। আর ডান হাত ফজলুকে দিলা (২, ১) এই অ্যারেকে সর্ট করে দেয়ার জন্য। তুমি যেহেতু তাদের বস, তারা উভয়েই সর্ট করে যখন অ্যারে দুইটা (৫, ৬, ৯ এবং ১, ২) পাঠাবে তখন তুমি জাস্ট মার্জ করবা। মার্জ করে আমার কাছে ১, ২, ৫, ৬, ৯ পাঠাবা।

বজলুকে যখন ৫, ৬, ৯ পাঠিয়েছ সে আবার কল করেছে তার বাম হাত ও ডান হাতকে যথাক্রমে (৫, ৬) ও ৯ দিয়ে। বজলুর বাম হাত লিটু সর্ট করে পাঠিয়েছে ৫, ৬ আর ডান হাত বিটুর কাছে ছিল শুধু ৯। তাই এটাকে সর্ট করে ৯-ই পাঠাবে। এই দুই অ্যারেকে মার্জ করে বজলু তোমাকে পাঠিয়েছিল ৫, ৬, ৯।

লিটু (৫, ৬) দুটি ইলিমেন্টের অ্যারে পেয়েও নিজে নিজে কাজ করে না। সেও বস সেজে বসে। সে কল করে ল্যাদা আর গ্যাদাকে। ল্যাদার কাছে পাঠায় ৫ আর গ্যাদার কাছে ৬। তোমাকে এক সংখ্যা বিষিষ্ট অ্যারে দিয়ে যদি বলি সর্ট করে দাও তাহলে কী করবে? ঐ অ্যারেটাই আমাকে পাঠিয়ে দিবে তাই না? কারণ এটা সর্টেড অবস্থাতেই আছে। ল্যাদা-গ্যাদা যখন ১ টা ইন্ডেক্স বিশিষ্ট অ্যারে পায় সেটাকে আর ভাগ করে কাউকে পাঠাতে পারে না। তাই এটাই তার বসের কাছে পাঠায় দেয়। দেখছো ডেসটিনির সিসটেম কত্ত সুন্দর!!! জাদুকরী এই সিসটেমে কাউকেই সর্টিং এর মত costly operation করা লাগলো না।

ল্যাদা-গ্যাদা সর্ট করে পাঠালো লিটুর কাছে। লিটু এই অ্যারে পাঠালো বজলুর কাছে। বজলুর কাছে তার ডান হাত বিটুও একটা অ্যারে পাঠালো। লিটু-বিটু’র অ্যারে দুইটাকে বজলু সর্ট করে তোমার কাছে পাঠালো। তুমি কিন্তু একটা অ্যারে দিয়ে কিছু করতে পারবা না। তুমি বসে আছো ফজলুর অ্যারের জন্য। এখন ফজলু কল করা শুরু করবে তার বাম হাত, ডান হাতকে। তারা কল করবে তাদের বাম হাত, ডান হাতকে। এভাবে কল হতেই থাকবে যতক্ষণ না পর্যন্ত অ্যারের সাইজ ১ না হয়। এরপর তারা স্টেপ বাই স্টেপ তাদের বসের কাছে সর্টেড অ্যারে রিটার্ন করতে থাকবে। এক সময় ফজলুর অ্যারেও সর্টেড হয়ে গেলে তোমাকে পাঠিয়ে দিবে। এরপর বজলু আর ফজলুর অ্যারে দুইটা তুমি জাস্ট মার্জ করবে। মার্জ করলেই সেটা সর্টেড হয়ে যাবে। এরপর পাঠিয়ে দিবে আমার কাছে।

আমার লেফট সাইডের কাজটা কেবল শেষ হল। এখন একই প্রসেস চলবে আমার রাইট সাইডের ক্ষেত্রে। রাইট সাইড যখন আমাকে মার্জ করে সর্টেড অ্যারে পাঠাবে তখন আমি তোমার অ্যারে আর রাইট সাইডের অ্যারেকে মার্জ করে দিব। ব্যস! খেল খতম!

এই ভয়ংকর (!) MLM process বুঝতে কোন সমস্যা আছে? সমস্যা থাকলে ব্লগ পড়ার MB ফেরত! 😛 আশা করি সমস্যা নাই। যদি সমস্যা না থাকে তাহলে ব্লগটা পড়া বাদ দিয়ে মার্জ সর্টের কোড করে ফেলতে পারো। কারণ এই বস্তুর নামই Merge Sort Algorithm! 🙂

Merge Sort Tree visualization. Photo Credit: interactivepython.org
Merge Sort Tree visualization. Photo Credit: interactivepython.org

যারা এখনো ব্লগটা কন্টিনিউ করছো তাদের জন্য কোড নিয়ে আলোচনা। উপরের সিসটেমে তুমি বুঝে গেছ নিশ্চয়ই যে, এখানে দুটি কাজ হচ্ছে। প্রথমত একটা অ্যারেকে ভাগ করে দুই জনকে দেয়া (Divide), দ্বিতীয়ত যে দুজনকে অ্যারে দুটি দিলাম তাদের থেকে অ্যারেটা নিয়ে মার্জ করা (Conquer). ভাগ করা এরপর জোড়া দেয়া। এই ধরণের কাজগুলোকে বলা হয় Divide and Conquer. Merge Sort Algorithm টা Divide and Conquer Method এর একটা উদাহরণ। ভাগ করা ও জোড়া দেয়ার জন্য দুটি আলাদা ফাংশন লিখা হল। একটা অ্যারে ভাগ করে দুই জনকে দিচ্ছি। তারা আবার প্রত্যেকে ভাগ করে আরো দুইজনকে দিচ্ছে। তার মানে এই ফাংশনের কাজটা recursive way তে হচ্ছে। এটি একটি রিকার্সিভ ফাংশন। Merge sort এর কোড করার জন্য prerequisite হচ্ছে রিকার্শন সম্পর্কে জানা। রিকার্সিভ ফাংশনের ব্যাসিক আইডিয়া পাওয়া যাবে এখান থেকে

void sorting(int startPoint, int endPoint)
{
    int midPoint;

    if(startPoint >= endPoint)
        return;

    midPoint = (startPoint+endPoint)/2;

    sorting(startPoint, midPoint);
    sorting(midPoint+1, endPoint);

    merging(startPoint, midPoint, endPoint);
}

শুরুতেই base case এর চেক রাখা হয়েছে। আমরা কখন একটা অ্যারেকে আর ভাংবো না? যখন ঐ অ্যারেতে একটাই মাত্র সংখ্যা থাকবে। যখন কাউকে একটা সংখ্যার অ্যারে দিয়ে কল করা হবে, সে সেটাকে আর না ভেঙ্গে তার বসকে বলবে “বস, আমার অ্যারে সর্টেড হয়ে গেছে!” অর্থাৎ সে তার বসের কাছে রিটার্ন করবে। আর কখন বুঝবো কোন অ্যারেতে একটাই মাত্র ইলিমেন্ট আছে কিনা? যখন তার starting index আর end index দুইটাই same হয়। এটাই বেজ কেসে চেক করা হয়েছে। sorting() ফাংশনের প্যারামিটারে পাঠানো হয়েছে ঐ অ্যারের শুরুর ইন্ডেক্স আর শেষ ইন্ডেক্স। যদি শুরু আর শেষের ইনডেক্সের মান সমান হয় তাহলে বসের কাছে হাজিরা দিতে যেতে হবে।

যদি অ্যারের উপাদান একটা না হয়ে একাধিক হয়। তখন অ্যারে ভাংচুরের ব্যাপারটা সামনে আসে। দুই ভাগ কিভাবে করা যায়? midPoint দিয়ে অ্যারেকে দুইভাগ করা যায়। মিড পয়েন্টের ভ্যালু বের করে দেখ আবার এই ফাংশনটাকেই কল করা হয়েছে। প্রথম ফাংশন sorting(startPoint, midPoint); সব সময় কাজ করবে বাম পাশের অ্যারেকে নিয়ে। আর দ্বিতীয় ফাংশন sorting(midPoint+1, endPoint); কাজ করবে ডান পাশের অ্যারেকে নিয়ে।

লিটু কর্তৃক ল্যাদা-গ্যাদা কল দেয়ার সময়টা মনে করো। লিটু প্রথমে ১০ নাম্বার লাইনে কল দেয় ল্যাদাকে sorting(startPoint, midPoint); ফাংশন দিয়ে। এখানে startPoint = 0 এবং endPoint = 0. উপরে গিয়ে দেখে আসতে পারো ৫ ছিল অ্যারের একদম শুরুর ইলিমেন্ট। লিটুর দ্বিতীয় কল ছিল ১১ নাম্বার লাইনে sorting(midPoint+1, endPoint); এই ফাংশন দিয়ে গ্যাদাকে। সেখানে startPoint = 1 এবং endPoint = 1. ল্যাদাকে কল করার পর সে চেক করে পেল শুরু ও শেষ ইন্ডেক্সের মান 0. সাথে সাথে সে লিটুর কাছে হাজিরা দিয়ে বলল আমার কাজ শেষ। লিটু কিন্তু তখনও মার্জ করে নাই। অপেক্ষা করছে গ্যাদার জন্য। গ্যাদাও চেক করে পেল তারও শুরু আর শেষের ইন্ডেক্স same. তাই সেও রিটার্ন করল লিটুর কাছে। ল্যাদার রিটার্ন করার মাধ্যমে লিটুর কল করা ১০ নাম্বার লাইনের কাজ শেষ হল। গ্যাদাকে ১১ নাম্বার লাইন দিয়ে কল করা হয়েছিল তাই গ্যাদা রিটার্ন করার সাথে সাথে ১১ নাম্বার লাইনের কাজও শেষ হল। লিটু কিন্তু জাস্ট ভাগাভাগির কাজ করেছে। বস হিসেবে তার কিন্তু আরেকটা কাজ বাকি। তা হচ্ছে ল্যাদা-গ্যাদার অ্যারেকে মার্জ করা।

যেহেতু ল্যাদা-গ্যাদা উভয়েই ফিরে এসেছে তাই লিটু এখন ১৩ নাম্বার লাইন দিয়ে কল করবে merge করার জন্য। প্যারামিটার হিসাবে পাঠাবে প্রথম অ্যারের শুরুর ইন্ডেক্স, দ্বিতীয় অ্যারের শেষের ইন্ডেক্স। খেয়াল করো, দুটি অ্যারের কথা বললেও অ্যারে কিন্তু একটাই! সব সময় কিন্তু পাশাপাশি ইন্ডেক্সগুলো নিয়েই কাজ হচ্ছে। তাই শুরুর ইন্ডেক্স যদি কখনো ৬ হয় শেষ ইন্ডেক্স হতে পারে ৭ বা ৮। বুঝাতে চাচ্ছি যে এটা সিকোয়েন্সিয়ালই থাকবে। এই ফাংশনে আরো পাঠানো হচ্ছে মিড পয়েন্ট। এই মিড পয়েন্টই হচ্ছে প্রথম অ্যারের শেষ ইন্ডেক্স। তাহলে দ্বিতীয় অ্যারের শুরুর ইন্ডেক্স কী? (midPoint+1) তাই না? এবার দেখি merging() ফাংশনটা কিভাবে কাজ করেঃ

void merging(int startPoint, int midPoint, int endPoint)
{
    int firstArrCnt,secArrCnt,i;
    firstArrCnt = startPoint;
    secArrCnt = midPoint + 1;

    for(i = firstArrCnt; firstArrCnt<=midPoint && secArrCnt<=endPoint; i++)
    {
        if(arr[firstArrCnt] < arr[secArrCnt])
            temp[i] = arr[firstArrCnt++];
        else
            temp[i] = arr[secArrCnt++];
    }

    while(firstArrCnt <= midPoint)
        temp[i++] = arr[firstArrCnt++];

    while(secArrCnt <= endPoint)
        temp[i++] = arr[secArrCnt++];

    for(i = startPoint; i<=endPoint; i++)
        arr[i] = temp[i];

}

পোস্টের দ্বিতীয় প্যারায় মার্জের যে সিসটেম বলা ছিল মনে আছে? লজিকটা হচ্ছে, দুইটা অ্যারেকে নিব। প্রতিবার দুটি করে ইলিমেন্ট নিয়ে নিয়ে চেক করতে থাকব আর নতুন একটা অ্যারেতে দুটি মানের মধ্যে প্রথমে ছোটটা এরপর বড়টা রাখতে থাকব। এই দুটি করে সংখ্যা নিয়ে চেক করার কাজ কতক্ষণ চলবে? যতক্ষণ উভয় অ্যারেতেই কোন না কোন ভ্যালু অবশিষ্ট থাকে। এই কাজটা করা হয়েছে উপরের কোডের ৭ থেকে ১৩ নাম্বার লাইনে। firstArrCnt = startPoint; এটা দিয়ে নিয়ন্ত্রণ করা হবে বাম পাশের অ্যারের মানগুলোকে। আর secArrCnt = midPoint + 1; দিয়ে ডান পাশের। দুটি counter এর মান assign করা হয়েছে অ্যারে দুটির প্রথম ইন্ডেক্স নাম্বার দিয়ে। লুপের কন্ডিশন দেয়া হয়েছে firstArrCnt<=midPoint && secArrCnt<=endPoint; অর্থাৎ প্রথম অ্যারের কাউন্টার বাড়তে বাড়তে মিড ভ্যালুর ইন্ডেক্স ক্রস করে গেলে অথবা দ্বিতীয় অ্যারের কাউন্টার বেড়ে বেড়ে দ্বিতীয় অ্যারের শেষ ইন্ডেক্স ক্রস করে গেলেই বুঝতে হবে যে কোন একটা অ্যারে খালি হয়ে গেছে। তখন লুপ ব্রেক হবে।

এই লুপের ভিতরেই if(arr[firstArrCnt] < arr[secArrCnt]) চেক করা হয়েছে। অর্থাৎ অ্যারে দুটির শুরুর মান দুটির মধ্যে ছোট বড় চেক করা হচ্ছে। প্রথম অ্যারের মানটা ছোট হলে তাকে একটা temporary ভেরিয়েবলে temp[i] = arr[firstArrCnt++]; রেখে দেয়া হচ্ছে। এই temp array-ই আমাদের কাংক্ষিত সর্টেড অ্যারে। দ্বিতীয় অ্যারের মানটা ছোট হলে সেটাকেও একই ভাবে রাখা হচ্ছে temp[i] = arr[secArrCnt++];। লক্ষ্য করো, অ্যারের ইন্ডেক্স ভ্যালুগুলো কিন্তু আলাদা। প্রথমটার কাউন্টার firstArrCnt আর দ্বিতীয়টার secArrCnt. মান অ্যাসাইন করার সাথে সাথে কিন্তু কাউন্টারের মানও increment operator (++) দিয়ে বাড়িয়ে দেয়া হয়েছে। যেন হিসাব করা যায় কোন অ্যারের কতগুলো মান নতুন অ্যারেতে বসানো হয়েছে।

কাউন্টারের মান বাড়তে বাড়তে যখন কোন একটা অ্যারের কাউন্টারের মান সেই অ্যারের শেষ ইন্ডেক্সের মানকে ক্রস করে যাবে তখন লুপ ব্রেক হয়ে যাবে। যদি প্রথম অ্যারেতে কোন মান নতুন অ্যারেতে নেয়া বাকি থাকে অর্থাৎ এখন পর্যন্ত যদি firstArrCnt <= midPoint হয় তাহলে বাকি মানগুলোকে ধরে সোজা কপি করে দেয়া হবে temp array-তে। কপি করা চলতে থাকবে আর কাউন্টারের মান বাড়তে থাকবে। যতক্ষণ না পর্যন্ত firstArrCnt বাড়তে বাড়তে midPoint ক্রস না করে।

while(firstArrCnt <= midPoint)
temp[i++] = arr[firstArrCnt++];

আর যদি প্রথমটায় বাকি না থেকে দ্বিতীয় অ্যারেতে বাকি থাকে তাহলে আর উপরের লুপটা ঘুরবে না। তখন কাজ করবে এই লুপটাঃ

while(secArrCnt <= endPoint)
temp[i++] = arr[secArrCnt++];

এতক্ষণে এই দুইটা অ্যারের সকল মান মার্জ হয়ে সর্টেড আকারে temp নামক অ্যারেতে স্টোর হয়ে গেছে। temp অ্যারের কোন ইন্ডেক্সগুলোতে বসেছে? প্রথম অ্যারের শুরু ইন্ডেক্স হচ্ছে temp অ্যারের শুরুর ইন্ডেক্স। আর দ্বিতীয় অ্যারের শেষ ইন্ডেক্স হচ্ছে temp অ্যারের শেষ ইন্ডেক্স। তাহলে এখন এই temporary array এর এই মানগুলো মূল অ্যারেতে কপি করে ফেলিঃ

for(i = startPoint; i<=endPoint; i++)
arr[i] = temp[i];

এরই মাধ্যমে লিটু সাহেবের কাজ শেষ হল। লিটু সাহেব arr অ্যারের 0 থেকে 1 এই ইন্ডেক্সগুলোর অ্যারেকে সর্ট করে বজলু সাহেবের কাছে হাজিরা দিয়েছেন (রিটার্ন করেছেন)। একই কাজ বিটুও করেছে। পুরো প্রসেস বজলু সাহেব করবে। ফলজু সাহেব করবে। তারা দুইজন তোমার কাছে রিটার্ন করার পর তুমি মার্জিং এর ফাংশন কল দিবা। এরপর আমার কাছে রিটার্ন করবা। আমার ডানহাত হাজির হবে আমার কাছে। এরপর তোমার (১, ২, ৫, ৬, ৯) এবং ডান হাতের (৩, ৪, ৭, ৮, ১০) দুটি অ্যারেকে মার্জ করার জন্য আমি merging() ফাংশন কল করব। এভাবেই একটা মার্জ সর্টের শুভ সমাপ্তি ঘোষণা হবে! আর এইসব মহা যজ্ঞের পরও Worst case এর ক্ষেত্রেও এর কমপ্লেক্সিটি O(n log n)!!!

পুরো কোডটা এক সাথে পাওয়া যাবে আমার গিট রিপোজিটরির এই ঠিকানায়।

অনেকগুলো সর্টিং অ্যালগরিদমের ভিজুয়ালাইজেশন দেখা যাবে এখান থেকে

২০০০ শব্দের চেয়ে বেশি শব্দের পোস্ট এটা। এত বড় হবার কারণ আমার বেশি কথা বলা (আসলে লিখা)। উদ্দেশ্য হচ্ছে অন্তত একজন যেন এটা পড়ে মার্জ সর্ট পুরোপুরি বুঝতে পারে। আর কোথাও যেতে না হয়। কেউ যদি এই লিখাটা পড়ে মার্জ সর্ট প্রথম বারের মত বুঝে থাকেন তাহলে কাইন্ডলি কমেন্ট করবেন। এটা আমার জন্য অনেক বেশি উৎসাহের কারণ হয়ে থাকবে।

ধন্যবাদ আপনাকে। আগাম ধন্যবাদ আপনার সুচিন্তিত পরামর্শ ও উপদেশের জন্য। 🙂

29 thoughts on “মার্জ সর্ট অ্যালগরিদম – Merge Sort Algorithm

  1. if(startPoint >= endPoint)
    return;

    ভাই return; এর কাজ কি? এইতা আসলে কি return করতেসে? return এর পরে তো কোন ভ্যালু থাকে অথবা কোন ভ্যারিএবল থাকে। কিন্তু এইটার পরে তো কিছুই নাই।

    1. এটা বুঝাচ্ছে এই ফাংশনের কাজ এখানেই শেষ। ফাংশন বডির এই লাইনের পরের কোন লাইন এক্সিকিউট হবে না।
      এই রিটার্নের ফলে এই ফাংশনকে যে কল করেছে তার যদি কোন কাজ বাকি থাকে সেই কাজটা এক্সিকিউট হবে।

      ল্যাদা-গ্যাদার উদাহরণের সাথে মিলিয়ে চিন্তা করতে পারেন। ল্যাদা-গ্যাদা উভয়ের ক্ষেত্রে এই ফাংশনটা প্রথম রিটার্ন করে। তার মানে রিটার্নের পরের লাইনগুলোতে ল্যাদা-গ্যাদার কোন কাজ নাই। যেহেতু কাজ শেষ তাই লিটু’র ফাংশনের বাকি অংশ এক্সিকিউট হবে। অর্থাৎ merging() ফাংশন কল হবে।

      আরো ক্লিয়ারলি বুঝার জন্য এই ভিডিওটা দেখতে পারেনঃ https://www.youtube.com/watch?v=TzeBrDU-JaY

      ধন্যবাদ। 🙂

  2. মার্জ সর্ট সম্পর্কে জানতাম কিন্তু এই প্রথম এত সুন্দর, সহজ আর ভালোভাবে বুঝতে পারলাম। অনেক অনেক ধন্যবাদ ভাইয়া। দারুন লিখছেন 🙂

  3. Thanks vai clearly bujanur jonno. age to algo dekhlei voypaitam. apnar post dekhe sikhar agroho ta bere gese .

    1. ধন্যবাদ মতামত জানানোর জন্য। ভাল লাগলো আপনার কথা জেনে। আরো লিখার জন্য অনুপ্রেরণা পাচ্ছি।
      সাথেই থাকুন… 🙂

  4. Thanks vai.আমাদের আগের ২ ক্লাসে লিনিয়ার ,বাইনারি স্রস দেকাইসে । আজ কুইক শর্ট
    দেকাইসে । পরের ক্লাসে মার্গ শর্ট দেকাইব । so অনেক ভাল হল । আমার পরের ক্লাস টা অনেক ভাল হবে । So lot of thanks vai.

  5. Fantastic, really great brother. Understood once again the merge sort and in more clearly. But if you change names with A, B or C i mean alphabetically, I would be more great cause names are more similar, hard to remember.
    And I obviously liked the “Alavola’s Example on Recursive” … laughed a lot.
    Good luck buddy.

  6. যদি কমেট’টি চোখে পড়ে!
    দয়া করে একটু বলবেন ভাইয়া……
    এই এলগরিদম বুঝতে আমার যে সমস্যা হচ্ছে-
    ১। ১০ নাম্বার লাইনে আমরা ল্যাদাকে কল করে পেলাম end এর মান 0, কিন্তু ১১ নাম্বার লাইনে গ্যাদাকে কল করার সময় end এর মান ১ হল কিভাবে? এভাবে ঠিক বিটু’কে কল করার সময়ও এর বাম ও ডান হাতের end এর মান নিয়ে আমার যত সব সমস্যা হচ্ছে।

    1. ল্যাদা বা গ্যাদাকে কল করে end এর মান 0 পাই নি। বরং ল্যাদাকে যেই অ্যারেটা সর্ট করতে দেয়া হয়েছে সেই অ্যারেতে একটাই মাত্র ইলিমেন্ট আছে। সেটা হলো মূল অ্যারের 0 index. ভাল হয় খাতায় অ্যারে এঁকে স্টেপ বাই স্টেপ ভাঙেন। পোস্টে এই অ্যালগোরিদমের ভিজুয়ালাইজেশনের লিংক দেয়া আছে। সেটা দেখলেও কিছুটা ক্লিয়ার হবে আশা করি।

  7. The long description was much needed and it was way more helpful then any other places.Though, I have little basic knowledge about merge sort ,but after watching this I have actually got the concept properly.
    Thank you.

  8. Thank you so much bhaiya! <3
    পুরো একদিন মাথার চুল ছিড়ে ঘাটাঘাটির পরও পুরোপুরি বুঝতে না পেরে যখন হাল ছেড়ে দেবো অবস্থা তখন সৌভাগ্যক্রমে বাংলায় সার্চ দিয়ে আপনার পোস্টের দেখা পেয়ে গেলাম। আমি আসলে algorithm এর explanation খুজছিলাম এবং চমৎকারভাবে আপনি তা বুঝিয়েছেন <3 যেখানে যেখানে কনফিউশন ছিলো একেবারেই ক্লিয়ার কনসেপ্ট পেয়ে গেছি। আসলে আপনাকে ঠিকঠাক কমেন্ট করে বোঝাতেও পারবো না কতটা উপকার করেছেন এবং পোস্ট বড় হয়েছে দেখেই ভালো করে বুঝতে পেরেছি। কোনো জায়গায় পড়তে বিরক্তিভাব আসে নি। আমাদের উপকারার্থে আরো এরকম পোস্ট করে যাবেন এটাই আশা করবো। আল্লাহ আপনাকে ভালো রাখুক! Thanks again!

    1. আলহামদুলিল্লাহ।
      ভাল লাগল যে লেখাটা আপনার কাজে লেগেছে। একমাত্র আল্লাহর রহমতের কারণেই এটা সম্ভব হয়েছে। আমার জন্য দুয়া করবেন। 🙂

  9. আমি অনেক চেষ্টা করেও মার্জ সর্ট বুঝতে পারছিনা।
    আমার প্রবলেম হয় মার্জ টা কল করার সময় merge(low,mid,high) এটা করার সময়
    প্রতি ফাংশন কলে দুইটা প্যারামিটার! কিন্তু
    পাঠাচ্ছে তিনটা মার্জে! যেমন মার্জ সর্ট ১ এ রিটার্ন করে
    মার্জ সর্ট ২ এর কল গেলো ঐখানে মিড+১,আর হাই গেলো
    এখন যখন কাজ শেষ করে এটাও রিটার্ন করবে তখন মার্জ ফাংশন কল হবে।কিন্তু low, mid, high kothai!

    মার্জ সর্ট ২ তে যে রিটার্ন করল এখানে তো দুইটা, low r high(mid+1=low,high)

  10. আসসালামু আ’লাইকুম ভাই। আপনার মজাদার কথা গুলা আর স্টেপ বাই স্টেপ বুঝানো টা সত্যিই অসাধারণ। আপনি আসলেই জোস ভাই। অনেক অনেক ভালো করে বুঝছি ভাই 😍😍😍😍। অসংখ্য ধন্যবাদ ভাই।

    শামীম সরকার।
    সিএসই, জবি, ব্যাচঃ ২০১৭-১৮।

  11. Brother you are awesome. I read all of your post it is very easy way to learn programming.

  12. আসসালামু আলাইকুম, ভাইয়া। আপনার লেখাগুলো খুব সুন্দর ও সাবলীল। কিছু জায়গায় আমার কনফিউশন আছে। লিটু যখন ১০ নম্বর লাইনে ল্যাদাকে কল করলো তখন স্টার্ট পয়েন্ট এবং এন্ড পয়েন্ট ০ বুঝলাম বাট গ্যাদাকে যখন ১১ নম্বর লাইনে কল করলো তখন স্টার্ট এবং এন্ড পয়েন্ট কিভাবে ১ হলো বুঝতে পারিনি। তারপরে ১৩ নম্বর লাইনে যখন মারজ ফাংশনকে কল করলো তখন স্টার্ট পয়েন্ট, এন্ড পয়েন্ট এবং মিড পয়েন্টের মান কত হবে? এবং সবশেষে যখন মারজিং এর কাজ শেষ হবে তখন কোন লাইন থেকে আবার এক্সিকিউট হয়া শুরু হবে? তখন আবার এন্ড পয়েন্ট এবং স্টার্ট পয়েন্টের মান কত হবে?
    আমি আপনার রিকারসিভ ফাংশন নিয়ে লেখাগুলো পড়েছি বাট মাল্টিপল রিকারসিভ ঠিকমত ধরতে পারিনা। উপরের বিষয়গুলো একটু ক্লিয়ার করলে অনেক উপকার হত।

Leave a Reply

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