মূল বিষয়বস্তু
মার্জ সর্ট সম্পর্কে আলোচনা
যেহেতু আমরা বিভক্তি এবং জয়(ডিভাইড অ্যান্ড কনকার) পদ্ধতি ব্যবহার করে সাজাবো, আমাদের ঠিক করে নিতে হবে ছোট সমস্যাগুলো কেমন হবে। সম্পূর্ণ সমস্যাটি হল একটি পুরো অ্যারেকে সাজানো। ধরি ছোট সমস্যা হবে সাবঅ্যারেকে সাজানো। বিশেষ করে, আমরা ছোট সমস্যাটাকে এভাবে চিন্তা করব, একটি সাবঅ্যারের থেকে পর্যন্ত উপাদানগুলো সাজাতে হবে। সাবঅ্যারের জন্য একটি চিহ্ন ব্যবহার করলে ভালো হয়, তো আমরা বলতে পারি উপাদান বিশিষ্ট একটি অ্যারের জন্য, আমরা বলতে পারি মূল সমস্যাটি হল
array[p..r]
হল ওই অ্যারের
সাবঅ্যারে। লক্ষ্য কর এই "দুই-ডট" চিহ্ন প্রকৃত জাভাস্ক্রিপ্ট নয়; আমরা এটা শুধু অ্যালগোরিদম বর্ণনা করার জন্য ব্যবহার করব, অ্যালগোরিদমকে কোড আকারে প্রকাশ করার জন্য নয়। আমাদের চিহ্নের সাপেক্ষে, array[0..n-1]
কে সাজানো।মার্জসর্ট যেভাবে বিভক্তি এবং জয় পদ্ধতি ব্যবহার করে:
- ডিভাইড কর
এবং মাঝে অবস্থিত সংখ্যাটি দিয়ে। এই ধাপটি আমরা একই উপায়ে করতে পারি যেভাবে আমরা বাইনারি সার্চে মধ্যবিন্দু বের করেছিলাম: এবং যোগ করে, 2 দিয়ে ভাগ করি এবং রাউন্ড করে নেই। - কনকার বিভক্তকরন ধাপে যেই দুইটি ছোট সমস্যা তৈরি হয়েছে সেই সাবঅ্যারেগুলোকে বারবার সাজাতে হবে। যেটা হল, সাবঅ্যারে
array[p..q]
এবং সাবঅ্যারেarray[q+1..r]
কে বারাবার সাজানো। - একত্রকরণ (কমবাইন) দুইটি সাজানো সাবঅ্যারেকে একসাথে মিলিয়ে একটি সাজানো সাবঅ্যারে
array[p..r]
তৈরি করা।
আমাদের একটি বেস কেস দরকার। বেস কেস হল একটি সাবঅ্যারে যার উপাদান দুইয়ের কম, এটা হয় যখন , কারণ কোন সাবঅ্যারে যার একটি উপাদান আছে বা কোন উপাদান নেই সেটা সাজানোই আছে। তাহলে আমরা বিভক্তকরন-জয়-একত্রকরণ করব শুধুমাত্র যখন ।
চল একটি উদাহরণ দেখি। ধরি একটি and )। এই সাবঅ্যারেতে কমপক্ষে দুইটি উপাদান আছে, আর তাই এটা বেস কেস হবে না।
অ্যারেতে
আছে [14, 7, 3, 12, 9, 11, 6, 2], তো প্রথম সাবঅ্যারেটি হবে সম্পূর্ণ অ্যারে, array[0..7]
(- বিভক্তকরন ধাপে, আমরা গণনা করে পাই
। - জয় ধাপে আমাদের দুইটি সাবঅ্যারেকে সাজাতে হবে,
array[0..3]
যেটাতে আছে [14, 7, 3, 12] এবংarray[4..7]
যেটাতে আছে [9, 11, 6, 2]। যখন আমরা জয় ধাপ শেষ করব, দুইটি সাবঅ্যারের প্রত্যেকেই সাজানো থাকবে:array[0..3]
তে আছে [3, 7, 12, 14] এবংarray[4..7]
তে আছে [2, 6, 9, 11], তাহলে পুরো অ্যারেটি হবে [3, 7, 12, 14, 2, 6, 9, 11]। - সবশেষে, একত্রকরণ ধাপে দুইটি সাজানো সাবঅ্যারেকে প্রথম অর্ধেক এবং দ্বিতীয় অর্ধেকে মিলিয়ে নিয়ে, চূড়ান্ত সাজানো অ্যারে তৈরি করব [2, 3, 6, 7, 9, 11, 12, 14]।
array[0..3]
সাবঅ্যারেটি কীভাবে সাজানো হল? সেই একই উপায়ে। এর দুইয়ের অধিক উপাদান আছে, আর তাই এটা বেস কেস না। এখানে array[0..1]
বা ([14, 7]) এবং array[2..3]
বা ([3, 12]) কে বারবার সাজানো হবে, আমরা পাব array[0..3]
যেটাতে আছে [7, 14, 3, 12] এবং প্রথম অর্ধেকের সাথে পরের অর্ধেক মিলিয়ে, পেলাম [3, 7, 12, 14]।array[0..1]
সাবঅ্যারেটি কীভাবে সাজানো হল? এখানে array[0..0]
যা ([14]) এবং array[1..1]
যা ([7]) কে বারবার সাজানো হবে, আমরা পাব array[0..1]
যেটাতে থাকবে [14, 7] এবং প্রথম অর্ধেকের সাথে পরের অর্ধেক মিলিয়ে, পেলাম [7, 14]।array[0..0]
এবং array[1..1]
সাবঅ্যারে দুইটি হল বেস কেস, যেহেতু প্রত্যেকের দুইয়ের কম উপাদান আছে। এখানে দেখানো হয়েছে কীভাবে মার্জসর্ট অ্যালগোরিদম কাজ করে:Most of the steps in merge sort are simple. You can check for the base case easily. Finding the midpoint in the divide step is also really easy. You have to make two recursive calls in the conquer step. It's the combine step, where you have to merge two sorted subarrays, where the real work happens.
In the next challenge, you'll focus on implementing the overall merge sort algorithm, to make sure you understand how to divide and conquer recursively. After you've done that, we'll dive deeper into how to merge two sorted subarrays efficiently and you'll implement that in the later challenge.
এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।