Divide And Conquer Algorithm Part 1

আমার ব্লগে আমার লিখা প্রথম এলগরিদম । জ্ঞান বিতরণ করতে বা ফাপর লইতে লিখি না। লিখা খারাপ লাগলে পরবেন না, তাও দয়া করে বাজে কিছু বলবেন না , আমি লিখছি নিজে অনুপ্রাণিত হতে, তাতে কারো উপকারে আসলে খুশি হব :) 

প্রথমে আসি ডিভাইড এন্ড কনকয়ার কি জিনিস, খায় না মাথায় দেয়, নাকি পড়ে ! 

প্রথম অংশটুকু হল "Divide", যা মানে ভাগ করা,  বুঝাই যাচ্ছে কোন সমস্যা কে প্রথমে ছোট ছোট সাব প্রোগ্রামে ভাগ করতে হবে যতক্ষণ পর্যন্ত সেগুলো সহজে সমাধান করা যায় । এবার ইন্ডিভিজুয়ালি সবগুলো সাবপ্রব্লেমকে সমাধান করতে হবে।

সব শেষে কাজ হল  "Conquer" . মানে সবগুলো পারসিয়াল সমাধান থেকে অরিজিনাল প্রবলেম এর সমাধান বের করা ! ( কত বাংলিশ  কয় রে !! )

• এবার আসি কেন আমরা এই প্রসেস ফলো করবো ? উত্তরটা খুবই সহজ, এই প্রসেস ফলো করতেই হবে এম্ন কোন কথা নেই, কিন্তু এই প্রসেস এর প্রধান সুবিধা হচ্ছে বড় বড় সমস্যা গুলোকে ছোট ছোট সাবপ্রব্লেম এ ভাগ করে সহজে রিকারসিভ্লি  সমাধান করা যায় । তাহলে মাথায় আসছে রিকারসন কি ? আজ রিকারসন নিয়ে লিখতে ভালো লাগছে না, যাদের কোন ধারণাই নেই, তারা এই পেজে ঘুরে দেখতে পারেন, রিকারসন  ।

তাহলে আমরা দেখলাম যে "Divide And Conquer Algorithm" তিনটি ভাগে কাজ করে ,

• মুল সমস্যাটাকে ছোট ছোট সাব প্রবলেম এ ভাগ করে ফেলে ।
• রিকারসিভ্লি সাবপ্রব্লেম গুলোকে সমাধান করে ।
• এই সমাধানগুলোকে কম্বাইন করে মূল সমস্যার ১টি সমাধান বের করে ।

আমরা এখানে "Divide And Conquer Algorithm" দিয়ে বাইনারী সার্চ আর মার্জ সর্ট নিয়ে আলোচনা করবো । :)

বাইনারী সার্চ 

প্রথমে দেখব বাইনারী সার্চ এর সাধারণ সমাধান ।
এই এল্গরিদমটি শুধু সর্টেট ডাটা এর উপর ই এপ্লাই করা যায় ।
ধরি ১টি সর্টেড অ্যারে a[] = {12, 23, 25, 37, 45, 57, 61, 77, 89, 117, 125, 131};

12    23   25    37   45     57     61  77   89   117   125    131

                                     

এখন আমরা এর সর্বনিম্ন সর্বচ্চ এবং মধ্যম সংখ্যাটিকে নিবো,  এ ক্ষেত্রে L ,M, H যথাক্রমে সর্বনিম্ন, মধ্যম এবং সর্বচ্চ সংখ্যার ইনডেক্স ধারণ করবে , এক্ষেত্রে 

 L =1      A[ L] = 12, 

M = (1+12)/2 = 6      A[ M] = 57,

 H = 12    A[H] = 131  

ধরলাম ইউজার ১২৫ কে খুঁজে বের করতে চায়, সে এখন ১২৫ কে M এর সাথে তুলনা করবে, 

১২৫ কি ৫৭ এর চেয়ে বড় না ছোট ,ঊঃ ছোট । 

তাহলে যেহেতু এটি ১টি সর্টেড ডাটা, কাজেই ৫৭ এর আগে কখনই ১২৫ কে পাওয়া যাবে না, তাইলে এখন সর্বনিম্ন ইন্বেডেক্স  ৫৭ এর পরের ইনডেক্স , অর্থাৎ L = M+1;

H আগের পজিশন এ থাকবে ,  আর M এর নতুন অবস্থান হবে (L + H) / 2;

12    23   25    37   45     57   61    77    89      117   125    131

                                                   

এক্ষেত্রে  L = 7,    A[L] = 61

 H =12,             A[H] = 131

M = (7+12) /2 = 9;      A[M]=89

এখন আবার ও ১২৫ কে A[M] এর সাথে তুলনা করবো। যেহেতু ১২৫ হচ্ছে ৮৯ এর চেয়ে বড় , এবং এটি ১টি সর্টেড ডাটা, কাজেই ৮৯ এর আগে আর ১২৫ কে পাওয়া যাবে না, তাই এর আগে আর খোজার দরকার নাই, তাই এখন

12    23   25    37   45    57    61   77    89     117     125      131

                                                                        

L = M+1 = 9+1 = 10      A[L] = 117

H = 12             A[H] = 131

M = (L+H)/2 = (10+12)/2 = 11  A[11] = 125

এখন ১২৫ ঠিক A[M] এ পাওয়া গিয়েছে ,

সুতরাং ১২৫ আমাদের এই ডাটা এর মধ্যে পাওয়া গেছে, এবং তা M নাম্বার ইনডেক্স এ আছে । 

এখন যদি এম্ন হত যে আমরা যে ডাটা খুজছি তা মাঝের সংখ্যা এর চেয়ে ছোট, তখন কি করা যেত? 

১২    ২৭   ৩৫    ৪২    ৬২    ৬৭   ৭৩

                                     

এখন যদি আমরা ২৭ কে খুজি তখন? 

আমাদের M এখন ৪২ এর উপরযা ২৭ এর চেয়ে বড়, কাজেই এক্ষেত্রে ৪২ এর পরে কখনই ২৭ কে পাওয়া যাবে না,

তাই H = M-1 = 4-1 = 3 নিতে হবে এবং M বের করতে হবে, এভাবেই পুরো প্রক্রিয়া চলতে থাকবে :) 

কোড

#include<iostream>

using namespace std;

int main(){

    int val, l=1, h=12, m;

    int a[] = {12, 23, 25, 37, 45, 57, 61, 77, 89, 117, 125, 131};

    bool ans = false;

    m = (l+h)/2;

    cout<<"\nEnter the Number u wanna search :";

    cin>>val;

        while(l<=h){

                m = (l+h)/2;

            if(a[m] == val){

                ans = true;

                break;

            }

            else if(val>a[m])

                l = m+1;

                else if(val<a[m])

                    h = m-1;

        }

        if(ans == true)

            cout<<val<<" found in "<<m+1<<" position";

        else

            cout<<"Not Found ";
return 0;

}