If you're seeing this message, it means we're having trouble loading external resources on our website.

তোমার যদি কোন ওয়েব ফিল্টার দেওয়া থাকে, তাহলে দয়া করে নিশ্চিত কর যে *.kastatic.org এবং *.kasandbox.org ডোমেইনগুলো উন্মুক্ত।

মূল বিষয়বস্তু

লিনিয়ার-টাইম মার্জ করা

মার্জসর্টে এখন বাকি আছে merge ফাংশন, যেটা দুইটি সংলগ্ন সাজানো অ্যারে array[p..q]array[q+1..r] কে সংযুক্ত করে একটি সাজানো সাবঅ্যারে array[p..r] তৈরি করে। আমরা দেখব কীভাবে এই ফাংশনকে যতটা সম্ভব কর্মক্ষমভাবে তৈরি করা যায়। ধরি দুইটি সাবঅ্যারের মোট n সংখ্যক উপাদান আছে। আমাদের প্রত্যেকটি উপাদান যাচাই করে তাদের সংযুক্ত করতে হবে, আর তাই আমরা আশা করতে পারি একত্রকরণের সময়কাল হবে Θ(n)। তো, আমরা দেখব কীভাবে n সংখ্যক উপাদান Θ(n) সময়ে সংযুক্ত করা যায়।
সাজানো সাবঅ্যারে array[p..q]array[q+1..r] কে সংযুক্ত করে array[p..r] এ রাখার জন্য, প্রথমে আমাদের অস্থায়ী অ্যারে নিয়ে সেখানে array[p..q]array[q+1..r] কপি করে নিতে হবে। আমরা array[p..r] এ মানগুলো রাখতে পারব না যদি না array[p..q]array[q+1..r] এর আসল মানগুলো ঠিকমত কপি করা থাকে।
merge ফাংশনে প্রথম কাজ হল, দুইটি অস্থায়ী অ্যারে নেয়া, lowHalfhighHalf, এরপর array[p..q] এর উপাদানগুলো lowHalf এ এবং array[q+1..r] এর উপাদানগুলো highHalf এ কপি করে নিতে হবে। lowHalf কত বড় হবে? সাবঅ্যারে array[p..q]qp+1 সংখ্যক উপাদান আছে। আর highHalf কত হবে? সাবঅ্যারে array[q+1..r]rq সংখ্যক উপাদান আছে। জাভাস্ক্রিপ্টে, যখন আমরা একটি অ্যারে তৈরি করি এর আকার নির্ধারণ করার প্রয়োজন হয় না, কিন্তু যেহেতু আমাদের অন্যান্য প্রোগ্রামিং ভাষায় সেটা করতে হয়, আমরা এটা করে থাকি যখন আমরা একটি অ্যালগোরিদম ব্যাখ্যা করি।
আমাদের উদাহরনে অ্যারে [14, 7, 3, 12, 9, 11, 6, 2] কে বারবার সাজানোর পর এটা দেখতে এমন হয়, array[0..3]array[4..7] (তাহলে p=0, q=3, and r=7) এবং এই সাবঅ্যারেগুলো lowHalfhighHalf এ কপি করে নিয়েছি:
array এর সংখ্যাগুলো ধূসর করে দেওয়া হয়েছে এটা বোঝানোর জন্য যে যদিও এই অবস্থানে মান আছে, "আসল" মানগুলো এখন lowHalfhighHalf এ আছে। আমরা ইচ্ছেমত ধূসর সংখ্যাগুলোকে প্রতিস্থাপন করতে পারি।
Next, we merge the two sorted subarrays, now in lowHalf and highHalf, back into array[p..r]. We should put the smallest value in either of the two subarrays into array[p]. Where might this smallest value reside? Because the subarrays are sorted, the smallest value must be in one of just two places: either lowHalf[0] or highHalf[0]. (It's possible that the same value is in both places, and then we can call either one the smallest value.) With just one comparison, we can determine whether to copy lowHalf[0] or highHalf[0] into array[p]. In our example, highHalf[0] was smaller. Let's also establish three variables to index into the arrays:
  • i indexes the next element of lowHalf that we have not copied back into array. Initially, i is 0.
  • j indexes the next element of highHalf that we have not copied back into array. Initially, j is 0.
  • k indexes the next location in array that we copy into. Initially, k equals p.
lowHalf বা highHalf থেকে array তে কপি করার পর, আমাদের অবশ্যই বৃদ্ধি করতে হবে (1 যোগ করব ) k এর সাথে যাতে আমরা পরবর্তী ছোট মানকে array এর পরবর্তী স্থানে কপি করি। আমাদের i বৃদ্ধি করতে হবে যদি lowHalf থেকে কপি হয় বা j বৃদ্ধি করতে হবে যদি highHalf কপি হয়। তো এই হল array তে প্রথম উপাদান কপি করার আগের ও পরের অবস্থা:
আমরা highHalf[0] কে ধূসর করে দিয়ে বোঝাচ্ছি যে এখন এখানে এমন কোন মান নেই যা নিয়ে আমরা কাজ করতে পারব। highHalf এর বাকি অংশ শুরুতে সূচক j, যেটা এখন 1। array[p] এর মান এখন আর ধূসর নেই কারণ আমরা এখানে একটি "প্রকৃত" মান কপি করেছি।
array তে পরের যে মানটি নিব সেটি কোথায় থাকতে পারে? এটা হয় lowHalf এর না নেওয়া প্রথম মানটি (lowHalf[0]) বা highHalf এর না নেওয়া প্রথম মানটি (highHalf[1])। আমরা একটি তুলনা করেই বলতে পারি যে lowHalf[0] ক্ষুদ্রতর, আর তাই আমরা একে array[k] তে কপি করব এবং ki এর মান বৃদ্ধি করব:
এরপর, আমরা lowHalf[1]highHalf[1] এর মধ্যে তুলনা করে দেখতে পাই যে আমাদের array[k] তে highHalf[1] কপি করতে হবে। এরপর আমরা kj কে বৃদ্ধি করি:
এভাবেই চলবে, সবসময় lowHalf[i]highHalf[j] এর মধ্যে তুলনা করব, ক্ষুদ্রতর মানটিকে array[k] তে কপি করব এবং হয় i অথবা j বৃদ্ধি করব:
পরিশেষে, হয় lowHalf এর সবগুলো বা highHalf এর সবগুলো array তে কপি হবে। এই উদাহরনে, highHalf সবগুলো উপাদান lowHalf এর বেশকিছু উপাদানের আগেই কপি হয়ে গেছে। সবশেষে আমরা lowHalf বা highHalf এর বাকি মানগুলো কপি করে নিব:
আমরা বলেছিলাম যে n সংখ্যক উপাদানকে একত্রকরণ করতে Θ(n) সময় লাগবে, আর তাই একত্রকরণ সময়কাল সাবঅ্যারে আকারের সাথে সরলরৈখিক। চল দেখি এটা কেন সত্য। আমরা একত্রকরণের তিনটে ধাপ দেখেছি:
  1. Copy each element in array[p..r] into either lowHalf or highHalf.
  2. As long as some elements are untaken in both lowHalf and highHalf, compare the first two untaken elements and copy the smaller one back into array.
  3. Once either lowHalf or highHalf has had all its elements copied back into array, copy each remaining untaken element from the other temporary array back into array.
এই প্রত্যেকটি ধাপের জন্য আমাদের কত লাইন কোড করা লাগবে? প্রতিটি উপাদানের জন্য এটা ধ্রুব সংখ্যা। প্রথম ধাপে array থেকে প্রতিটি উপাদান হয় lowHalf বা highHalf একবারই কপি করা হয়েছে। দ্বিতীয় ধাপে প্রত্যেকটি তুলনার সময় ধ্রুবক, যেহেতু এখানে শুধু দুইটি উপাদানের তুলনা করা হয়েছে এবং প্রত্যেকটি উপাদান একবার তুলনাতেই "পাওয়া" যায়। দ্বিতীয় ও তৃতীয় ধাপ মিলিয়ে প্রত্যেকটি উপাদান আবার array তে একবারই কপি করা হয়েছে। যেহেতু আমরা প্রতিটি উপাদানের জন্য প্রতি লাইন কোড ধ্রুব সংখ্যক বার চালাব এবং আমরা ধরে নিচ্ছি সাবঅ্যারে array[p..q] তে n সংখ্যক উপাদান আছে, একত্রকরণের সময়কাল প্রকৃতপক্ষেই হচ্ছে Θ(n)
In the next challenge, you'll implement this linear-time merging operation. With the two challenges combined, you'll have implemented the complete merge sort algorithm.

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।

আলোচনায় অংশ নিতে চাও?

কোন আলাপচারিতা নেই।
ইংরেজি জানো? খান একাডেমির ইংরেজি সাইটে আরো আলোচনা দেখতে এখানে ক্লিক কর।