Daffodil International University
Faculty of Science and Information Technology => Science and Information => Topic started by: Mehedifaruk on October 14, 2017, 10:01:09 PM
-
আজ যে এলগরিদমটা নিয়ে আলোচনা করব , সেটার নাম মার্জ সর্ট এলগরিদম । শুরুতেই কিছু কথা বলে নেয়া যাক ~ একটা সমস্যা সমাধানের জন্য কয়েকটা এলগরিদম থাকতে পারে । এই যেমন সর্টিং এর জন্য
Bubble Sort , Insertion Sort , Selection Sort , Quicksort , Mergesort , Heapsort এলগরিদম রয়েছে ।
প্রশ্ন হচ্ছে এতগুলো এলগরিদমের মধ্যথেকে কোনটা বেছে নিব ? এলগরিদমের দুইটা বৈশিষ্টের উপর ভিত্তি করে আমরা বেস্ট এলগরিদম বেছে নিব ।
Correctness
Efficiency
কিভাবে একটা এলগরিদমের কারেক্টনেস এবং ইফিসিয়েন্সি বের করে সেটা নিয়ে আরেক দিন লেখব । সর্টিং এলগরিদমের মধ্যে সবচেয়ে কার্যকর এলরিদম হচ্ছে Mergesort এলগরিদম । চলুন Mergesort এলগরিদমের সাথে পরিচয় পর্ব শেষ করা যাক । Mergesort এলগরিদমকে Divide and Conquer এলগরিদমও বলাহয়ে থাকে ।
১৯৪৫ সালে John von Neumann নামের হাঙ্গেরিয়ান - আমেরিকান গণিতবিদ Mergesort এলগরিদম আবিষ্কার করেন । চলুন শুরু করা যাক
ধরুন আপনার কাছে আনসর্টেট একটা array আছে , নিচের চিত্রে খেয়াল করুন
(https://lh3.googleusercontent.com/H9caCAA_SQHGv_eqGKccSvopgMtLjPu7s2tFgjwBlyWw4URLQIeQCBqGK-2R7lNA-iZ0Xu4WmSHrcFDNk75PWxV1qJNNXupEMXdxXSW0Q2cp5sPFMnIXMIStYiRf7dWCfoiymygZz8rx3dV2kMFJmfoXModAkguXPXxMhlJH9IOBz-toZiWhq7YnnFXx6NFvN4TVj_UYA_RhrsuUGkt2QGQO0qs4blRBrg7mBKppteQaNG960jUwLyxqnEXBhY9o94i-O0z2eYiS4hUUBjr3s48drcMInnbQTip--FSzQ6yi88BRKeQhdT329jMd6yNsnXIm0yBNuSA4AFAPN6Ofv93yfnOGqILwersoIVuM8J7oxHV20WhjqWO8KzQzCQmN_2nKXbUk4ie3AgYl7LJQRczAP5MOC7hOVZXAjP477sPOn5QZLOk0r_38nzpgWapBlnm8amoArKaa2K_vIFnDpLX2uznDGJM5dChu5ntJQvgLJj_59lxOgEIL4KRb3ES_ltI4_k77HX_s8SoTSJztLIbQJA0LYGSHf74JIT8hkwhQljOr3Ux3pIabMWZ2YSkZw5CjiDdauAILEV84A5N3NxiBqamdl73ZnFtV5Xnm3A=w722-h51-no)
আমরা গত পর্বে দেখেছিলাম কিভাবে বাবল সর্ট এলগরিদম ফলো করে খুব সহজেই একটা আনসর্টেড অ্যারে সর্ট করা যায় । Mergesort এলগরিদম পুরোপুরি ভিন্নভাবে কম সময়ে এই কাজটা সম্পন্ন করে ! এজন্য Divide and Conquer নিয়ম ফলো করতে হয় ।
প্রথমেই আনসর্টেড অ্যারেকে দুই ভাগে ভাগ করে নিতে হবে , নিচের চিত্রে খেয়াল করুন
(https://lh3.googleusercontent.com/iweAy_U7C2o4Ou2MKp4siFdasq7rph5Xs2beXY7CqlCaMHM4THiBI8rzs1oWygd-VsVH-F1bNKSbI_PhPS9SoHJTzkI9LosZ4VPLsoe4mbnp4tqSZti_t3fJQGLjV1kwxPnHRMKKt4xtXmX3qmdNGop71fcYTOAfXTcpXpttK5nXUF4Y-rITb4dUkazdPLkpojKRI2dLiwnSrVdjkUGB8vzdKLsj8XE3LObwh05IGOdKhenlC4MAUbgcb56XHUP7CPWEtobYPH9XQthPBP12JSwzyL4xWnmBC172HFrpUyfPv_nnTjAzowAu0IBd6b5YwYo-yLuULI6bgtww7h9qqXH4CcKuZWfWC07nzUTZlBtGKjlhv74KBQl12EsIYPijNmJvjdIprd9ofp4uw2CdUubWX3h4_TlfFHcQIPt1g44C28nVh61P9Tf0qYJgAf8xQ9D828jDmHj7wUUh3pWhzY-xsiPZDNguvlC2vApmKUYtphqgeNEBsTQHhFa2GTQqRb3h3ysNhbwLGkQfLXNnvqBngCQWDTSygJbUE4w52tT7hq-lf5du7qqrN-YJyvd6LBDGDQ_FrN9Byk20XvD6WFjyzTsVjqzCwKMC-zAlww=s800)
এভাবে যতক্ষণ ভাগ (ডিভাইড) করা যায় , মূলকথা হচ্ছে আমরা মেইন লিস্ট থেকে সাবলিস্ট তৈরি করে বড় সমস্যাটাকে ছোট ছোট অংশে ভাগ করে দিচ্ছি । ছোট অংশগুলোকে যখন সমাধান করে মার্জ করব , তখন আমরা বড় সমস্যাটার সমাধান পেয়ে যাব । চলুন উপরের দুইটা সাবলিস্টকে আবারো ডিভাইড করা যাক
(https://lh3.googleusercontent.com/kCYBGu0VZIKdGHvsi0Xz__lsJH1asqOAeXJ_kbko9XOr0jFbsPqtZPsJq8EveF8EuLA2eB251hphgBc8XHP-siw7WNiZCQia_3m80DpBG2FN5SsjyWOytwpp3GFpSDsS8qMkmXmrAOMHttesH2DBTD1mp2ShlAbwQmXo9KidBZiK03wmV-0mxEBil9bS7K-qlojKhtwNBm_ZIsXPpvxAEC_GLFO8pWHNTJdBl0QM8KXc-ol_kZNto_usVMuuojIfFP8LMfv1KTDD7j5mIdv8MtaFI-7pQor2MbZ1o-HyZ32HjHWNjy5I57QpDLXwf0yVqHDkUdofECo7BmEG94HGSzOP07tomQkx5cX0F_ZiShA4YIaiFQ08lk6cPhLIyxAH7MSQ-hm14fGUB9MGhcRUnAKtbSpqFs-6s_qVpd0aRNH5AaDbgA8IXVZwuW03AMC3RYWu70bJ1zuxsEoUizbCzxNzqg16G3EDAZ53rhEZXqfFAbYclodAyz3tEIiMNqRHyiSJW_V1KLVi2KtDDDr6TNbTOJD5SxwWQa7XvmboYkDD4RugQ2-xY3oFykR9nmIc0SgARx5Dca1gQls_K18XZ528bGXakC_KmLh0TjMLnA=s800)
এভাবে আমরা সাবলিস্ট তিরী করতে থাকব যতক্ষণ পর্যন্ত আমাদের সাবলিস্ট বানানোর অপশন থাকবে , নিচের চিত্রে খেয়াল করুন –
(https://lh3.googleusercontent.com/LkjVNd0wIxJTF7Wnn0DAjCPaLCrQEVDOFvlzQ6dHtbXnsmdOa5JrtVsqHHrmLBh1gmlk1whHcofW1-fjipnlMGnWJ3zEg855NNEicUFjb2i4Z9akleEmeXiZI3OQES4HLDtky9QOuoFnyHXeZEwAMoxSUHBpGw0Ue3rDTi6B0xedXOu4_ReIJXynuxPUQgFx_qVUDNZo8SYM2Cc5TgiTFN-ngHAkrrFzFsQTGxEBJ8clrjVLvQu739tMukdev14iEJnkEUlh4CKce8pUZwPDTvBLVjiLjq8ppvJU0EFy4fdyEKBiBmU0Pbecb5xDGv_Pi0qjpZ09RnTr-6bVgKIADeHVJaIWDqPZm8uTZ9wnEFkko8QugvE20v1MXS8YG26VoYyeSrUZxTmb7A8fsEFO-Lq-ou9Xew2nKs7WcS2STWDrD_ARIQwPTGuSPVftBgJ4QLoZrGk1E8YuxpIxd5zAY7h0YjflmZGsqvXECEidPfthKsBVFRf-71KODyYKcVEtPPpgmQ_JiMNoYdbwxLfsnbkN59MgWwY6ZPP0QYKVgcTRvL0V1SN_s-kaUmuGBdRGFfL-yk49c_ijTWT0ym12dyYO_HFX9EnDQgWQe0kYwA=w328-h71-no) (https://lh3.googleusercontent.com/GeV8KX4FFhKzbHUw5AYxcc87DYTQJyBSBz5pUzomldHqChzHx5zJ7b3-glfCyNF55YNQSna51EifMOVrepmlvWoZMTO-IKuWl_6_bJcsa9XE5Qn1JbPhM5qK667uf84FL2BZzPaV15GtcAJRpcaAQGOwWw7Jtr3Kaj1A71L4QnUN_XUtrQDV233dh0Sl5qhKOcYcpSI9s_NLQSFMRROcFr_IPgNvYEF9nuKGTpEIffpn1O7OGHOftBlzXn_4ls-Ec1vOH9T5PR3H6FMuVRszPcWjshejy_1N9TbyTmtt7yOMtef6WEDJfDTKtyImJy1s7y235JoLLjmJIDaP9FQ__h55UlEKz0J2C2vMCZRgLf79j-NiM2LHiuo4Qrwu2QHwS88tq0jzG7W1OY1JCe8KqUlfjc64be9wjEa40ojbUJoLWSlQ3bSUWwTquvhQYQlEobeMOm7qkL3pKciNtI6wl-IDRM9b7lMWemnZdzbN6HdyJWR5xOFyeQvXAGR-g019SYci-0YtkRhmItp4C3-4NfRkvVdhGIoOTjUliCPyQnQMrHCKPOgCuvrvN4x1W6lmkvCgAwr1uQtcZmwRuLCs_49bHhMmt6I5kuNeuewxFw=w349-h79-no)
এবারে আর কোন সাবলিস্ট তৈরী করা সম্ভব নয় , এবারে ভাগকরা সর্বশেষ দুইটা এলিমেন্টের মধ্যে কম্পেয়ারিং শুরু করব । যেহেতু ২ < ৪৫ , সেহেতু এখানে কোন পরিবর্তন হবে না । ২ আর ৪৫ কে আগের অবস্থায় রেখে দিব । আবার ৫ < ৫১ তাই এখানেও কোন পরিবর্তন হবে না , তাই তাদের কেও আগের অবস্থায় রেখে দিব ।
এবারে ডান পাশের ১ এবং ৩৫ এর মধ্যে তুলনা করব , যেহেতু ১<৩৫ সেহেতু ১ এবং ৩৫ আগের অবস্থাতেই থাকবে । এবার ৬২ ও ১৫ এর মধ্যে তুলনা করব , এখানে ৬২ > ১৫ , তাই ১৫ আগে চলে আসবে এবং ৬২ পরে চলে যাবে । নিচের চিত্রে খেয়াল করুন !
(https://lh3.googleusercontent.com/ehteosHugnzXxcCYYTHdmKD3p5ubWNXT1GTnroKsDducx6LntzA7_83B74tMdwQBImTU9AuN1zu7AIlck20IBDNrfrSC7Y5BXYmA6q6fLaXnMcxaNnRruTmyjeYsdYPT50Sf85vLy5RNTSjsdFC5DY9yysQQNbtoeLta97kPfF7kaiQgYPddJffJG5TxLjNFYXsUdQzIgmD-asulYYPrRZ15HaI14G-JnPbhL8Gcf2KwrDk49o93L148s7wqzMZUYrKEeB1y5vi6pLrdDZft0SpG-0Sqym11xK34wUYoXAAmvyUQZUOGUs0nrHhoqpUe-t0dSsubRCXwesagwbaVTTsDcKydxpIVQ2eWXj-ruy8vGGZ89HBqwfr7jwVTm0-d67F2_vxowQ1j3ehZ-d6gB60thmg0NlWT0PA11UYj3bIr9fRA7qXiNNPh3PM6xpDhMKTiyTeKnSsLICVGLu1WU04fzaaB9adSOIVA2Bvzdryn-PvE-R54dRf7VvBBi7B69KRe9siDAUzUT5qlYC9xmpyCLjhBtcyihy-hbOfAXF3S-h9RZQWhTKkU9SAdlF9H-sawxenwcTM4oitNNT1Nw3rNCD35MYLfbyHGoE2f5g=w256-h55-no) (https://lh3.googleusercontent.com/KWjAfhC27uBXYF1kWgyb2jPfcde1crPq3_807lUbWoyr0bxm1uHHNpHPlnaQSRd2kaIiBrFc0yUigJvK8kP8Sp-_J4wQJaF3pXYhz21idXphND4ZbIq3HZnfXMJLdYj8N0gU9NQHu3_sqpkO9EQp-2cozF7sOeZGfhXC0nQ288_g17iEy-BUlhsaMZAIc28wzXmgTBRM76vJ578kUnjogdJVE83kLltffVLaF0WA4vsYNQJrm6LhPpPWNkq7noG6WGtRVjMBuNVWe5AtDiP9lbd8yBunpGr9djEyALHiVjb33Xu0XPkNVvmVrJo7matFJ6Ut6ddKKQByhB-nwWtiYdDIObMtURgH8BVQYUZYaJxqA3JgvpEyCWHQ3HMdDz-LU6-522P25XOejH_oMaKh4dC-kXaHj5tp7z88t60MP7gNPlVHAhGGTSZwl4dnTjPGCvF51kcuJgxAH3sGn957Lu69YNSukMaAiZ7tkmwU4DTEAokvVT8Q_9miMM-ivhT7UQME9wGbFppSfLOLj71azr9qorPqFDSPKanJamzD6yKebb5fMheZMAjd4uRaWPYvAWJtZ7LZWfpnnlsvGNd1HEfVmKLWjdEBvSf84OtVyQ=w274-h64-no)
এখন আমাদের হাতে দুইটা দুইটা করে মোট চারটা সেট রয়েছে যেখানে সবাই সর্টেড । এরা মূলত আমাদের ভাগকরা সাবসেট ! এবার বাম পাশের দুইটা সেটের প্রথম এলিমেন্টগুলোকে কম্পেয়ার করে সর্ট করব । প্রথমে ২ আর ৫ এর মধ্যে কম্পেয়ার করব , যেহেতু ২< ৫ তাই ২ প্রথম স্থানেই থাকবে ! এবারে ৫ এর সাথে ৪৫ কে কম্পেয়ার করব । এখানে ৪৫ > ৫ , তাই ৫ চলে আসবে দ্বিতীয় স্থানে । বাকি রইল ৫১ , এবার আবার ৪৫ এর সাথে ৫১ কে তুলনা করব । ৪৫ < ৫১ তাই ৪৫ চলে আসবে তৃতীয় স্থানে এবং ৫১ চতুর্থ স্থানে ।
(https://lh3.googleusercontent.com/MUWFIA1j6I6sxaXLIlt7TOQmQXZBm32CNCvbUDreghfdJXcH5uITe6Q611VV46chMbf_fxApYY6ht2MZ09Ti0Ml0NsO4REjSj7-jHRn5VMsQUdP9uKvKHwchwFuvlP8TpqTIytLIw0CtNzY9g18qhP-bSLlU7me9P0gSIE0CtmpNSM7EW4RTAqf42uUG7iYu_0jNh9dHcBb3r-c1H_nH1MImsYeQjB_vsnFzZFct83Bjw7K0lVIJxmiE9m7VRgLmC5qM6D0nXsvJM4oy3yIZF9nREsFDxEq3mUxPWQu4VQ1a1vYH8eiFWUb9BnZ30fLS12YdhMmz47AU8uJp7FY6bSohAGUA30JlmHWIqTRrqPeQGC8CI8sk7t6IFJicrVFbk4ttPJmT4vQM6PFAKrj2wxNNKb6Qak5FYGs1i7MtzOQqBsCm3A8PWwtN77FP268K4R9ec8KlUhQd_JcFghcwqEzWvYMEEbOY05_WHM8gRSXVnbWC_WRyIK4BEsmDqKo64TFmN2uXkLs0NOTG8rgbIqUarwb1YqAhphq5Elb9uTt-bCz1_1PsI1H3IVdiJrPa48e2Np61gb3d5oqhInJeOgJUiOWrKjBUVIhbi2T6Lw=w349-h52-no)
এবার বাম পাশের মতই ডান পাশের দুই সেটের প্রথম এলিমেন্ট একটার সাথে আরেকটার তুলনা করে সর্ট করব । প্রথমে ১ এবং ১৫ এর তুলনা করব । ১ < ১৫ তাই প্রথমে ১ থাকবে , এবার ১৫ এর সাথে ৩৫ এর তুলনা করব । ৩৫ > ১৫ , তাই ১৫ চলেযাবে দ্বিতীয় স্থানে । এবার ৩৫ এর সাথে ৬২ দিয়ে তুলনা করব , ৩৫ < ৬২ তাই যথারীতি ৩৫ তৃতীয় এবং ৬২ চতুর্থ স্থানে থাকবে । নিচের চিত্রে লক্ষ করুন ~
(https://lh3.googleusercontent.com/_J5ZQ2UmykMQDswADxFMki1qhRrXzNIGnACtEjc7bXLyCDqkdaCKhq30sbvBaHmA9cgIfKLwFV-m1MFkY1ZmC0NBWbtDxQRlQjU_Stlq1O8AWsMQF0BhxXd_RBXsfW-kg7UzzqRU3JW165mT7aviG6aspNHfceqjlo5JRvUgS4tULTnKj93JeBbgnoipBgHbBldEmQ_58sRGpfkma1CjaCcAt6Qu2CBR7aauQrFgdhlfmHKFv7TQ4Q5VJtFLAiefTINmxp37O6aqoIiuuwZyuME5s4dYNDLaEIkA3SqHUsPJNVNOhjbsLfmER4ZMJ6RHTZSlKDzc6uycXe2mpEn7Phfn90Vp32erOXfDhL11t3NnSvJdrZmn3I53ItbHihh8iKzoRPjn9IRJU11Jk1bWBQ9ZwARlaJ8qwfeUx017bnxZWfb1UfRMCnkGr_mfxNtaLbvtmvTCdz68bg2uau9DbFJcFttyiRppSXQp_IlA6OjI9EwbdXeJNsELlLviKn8Jje1Qf1cNdHjx8PBykMB4qA53jefl9MNwG2Sb5lk1xMz6t2m-h789dIiT_i-UyjmbcjFtMhpkhFUikwm13zp4qcleJYHfklkwUcES57jUcQ=w350-h49-no)
এখন আমাদের হাতে আছে দুইটা সেট , যাদের কে আমরা এতক্ষণ সর্ট করেছি ।
(https://lh3.googleusercontent.com/ahOIC4c9kMtTw0TwaGTotnunE6YN7ZGZOOM2g8ilYAwl-0ElXJArJa5ePAba3garzoEQ8IB9AkgjAh9_dd_bjH7O8qqEazHGdETzZM5ykxmkkTNIKVVVm4cnW3qNVN5izlrQ_xMijTqIXuA7q4NTNgRAzmkIEe-2WpB5G-Fo87grNsErCSwPW_rXFs4kNS8pfg5FYNMCzt24RtBEXFE-v-7rLA--fUmb8SO6aLrjgsu3-hhJXNcg2hpziywkoPx-uMrXPk6TDb0v5C0uHHFPeceibgVJ20X5kq0xuZXLzChsSnOqxZ6denIIntXtc55S6RXXD32THT8MnWLD2xRduJ7ZsrqDOBa29xbH0naFqSjT-9ITjs0JTO8yAuiuiAHCg324twy1QY-5EeAE8jYb_rfVIoFdT8njkhreuDQoRQGmh2Go8wjAhBQCykf_m0lOJKoeoEnnVAGd8hwXRmHox_HzMTl8m0r5bfAVkwaIEEAwoxaNxSi-22JcKA2xE4bIzjQHnCP73w2JZEIGQ78Zzet-JfuVDmnpv93pFFhnWNwxEXoPzQMNeljWMyqELiky_2JNmJu76fW1HAy1QxkWseLVRj2JntymWUefebPOew=w776-h51-no)
এবার আগের মতই দুই সেটের প্রথম দুইটা এলিমেন্ট একটার সাথে আরেকটার তুলনা করব , প্রথমে ২ এবং ১ এর তুলনা করব । ২> ১ তাই ১ চলে আসবে প্রথমে । এবার ২ এর সাথে ১৫ এর তুলনা করব , এখানে ২ < ১৫ তাই ২ সামনে চলে আসবে । এবার ১৫ এবং ৫ এর তুলনা করব , ১৫>৫ তাই ৫ আগে চলে আসবে । এবার ১৫ এর সাথে ৪৫ এর তুলনা করব , ১৫ <৪৫ তাই ১৫ আগে চলে আসবে ।
এবার ৪৫ এর সাথে ৩৫ এর তুলনা করব , ৪৫ > ৩৫ তাই ৩৫ আগে চলে আসবে । এবার ৪৫ এবং ৬২ এর তুলনা করব , ৪৫ < ৬২ তাই ৪৫ আগে চলে আসবে । এবার ৬২ এবং ৫১ এর তুলনা করব , ৬২ > ৫১ তাই ৫১ আগে । এবারে ৬২র সাথে তুলনা করার মত কোন ইলিমেন্ট নেই তাই ৬২ সবার পরে চলে যাবে । নিচের চিত্রে খেয়াল করুন ~
(https://lh3.googleusercontent.com/BjB28eKKLywM1mKeeP0xsEI34KIIRLyCkOQHVhDxAo-lzQYFbxBvdVCbGukmf3Mytd74dZ5agZ52z-CoZ1RxwMV4ZF_mNQSHaffGCyMIWKI40ssZUXoLrygB3-mH0g523j07HDZ3Acvb92qkyLHu3e19yMleIRVp3p1j1qTEIDFuxPV6RskU62A2SBSDEpZNMSPzNKAL4vofoiM6m02LzF4lZJCjnNBUhZKt7BasPIvdnSk82CFumV99VLi_4RiMk9HT9hdBzF9lcF3HMVrWDO1bLvKS5NUqbzHDMRn_SYTOf6eahp0xW3wep6M9mMPl_Ntixz1iGbtNHS99g8wtIKRnGN8q7Huiw_5rzN6RAAquq3U_ZQhG3lUYYl5M2W3uhLFisPyWmBb5DjeOJYveaPHzrVLqQJE-F87fYT0It--jyzWFWIF0jdHJ-uSPpNOIkJVbC1pvceaACSqkZ0F8-l7MO_2fWfLakucXH5ffsh-JL4_SHrYn4Qbx1yRdIq4FNG7ztJt3LoyahosRdWIEn0QklAHzSWmERrkCH-bnttmbdX-BwE202flmHqaE2F2ZuZBibgl1EyRjMfDnuA34_IR7VyS_6jFIMfabe78dTw=w719-h47-no)
পুরো ব্যাপারটা হচ্ছে , প্রথমে আমরা অ্যারেকে দুই ভাগে ভাগ করতে থাকব , যতক্ষণ পর্যন্ত সিঙ্গেল এলিমেন্ট না হয় । তার পরে সর্ট করে করে নিচ থেকে উপর পর্যন্ত যাব । এটাকে রিকার্সন বলা হয় ।
আর এই পর্যন্তই , কোন প্রশ্ন থাকলে কমেন্টে অথবা মেইল করতে পারেন !
http://facebook.com/sajibcpi (http://facebook.com/sajibcpi)
-
:)
-
Thanks.