মূল বিষয়বস্তু
লিনিয়ার-টাইম মার্জ করা
মার্জসর্টে এখন বাকি আছে সংখ্যক উপাদান আছে। আমাদের প্রত্যেকটি উপাদান যাচাই করে তাদের সংযুক্ত করতে হবে, আর তাই আমরা আশা করতে পারি একত্রকরণের সময়কাল হবে । তো, আমরা দেখব কীভাবে সংখ্যক উপাদান সময়ে সংযুক্ত করা যায়।
merge
ফাংশন, যেটা দুইটি সংলগ্ন সাজানো অ্যারে 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]
কপি করে নিতে হবে। আমরা array[p..r]
এ মানগুলো রাখতে পারব না যদি না array[p..q]
ও array[q+1..r]
এর আসল মানগুলো ঠিকমত কপি করা থাকে।merge
ফাংশনে প্রথম কাজ হল, দুইটি অস্থায়ী অ্যারে নেয়া, lowHalf
ও highHalf
, এরপর array[p..q]
এর উপাদানগুলো lowHalf
এ এবং array[q+1..r]
এর উপাদানগুলো highHalf
এ কপি করে নিতে হবে। lowHalf
কত বড় হবে? সাবঅ্যারে array[p..q]
এ highHalf
কত হবে? সাবঅ্যারে array[q+1..r]
এ আমাদের উদাহরনে অ্যারে [14, 7, 3, 12, 9, 11, 6, 2] কে বারবার সাজানোর পর এটা দেখতে এমন হয়, , , and ) এবং এই সাবঅ্যারেগুলো
array[0..3]
ও array[4..7]
(তাহলে lowHalf
ও highHalf
এ কপি করে নিয়েছি:array
এর সংখ্যাগুলো ধূসর করে দেওয়া হয়েছে এটা বোঝানোর জন্য যে যদিও এই অবস্থানে মান আছে, "আসল" মানগুলো এখন lowHalf
ও highHalf
এ আছে। আমরা ইচ্ছেমত ধূসর সংখ্যাগুলোকে প্রতিস্থাপন করতে পারি।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 oflowHalf
that we have not copied back intoarray
. Initially,i
is 0.j
indexes the next element ofhighHalf
that we have not copied back intoarray
. Initially,j
is 0.k
indexes the next location inarray
that we copy into. Initially,k
equalsp
.
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]
তে কপি করব এবং k
ও i
এর মান বৃদ্ধি করব:এরপর, আমরা
lowHalf[1]
ও highHalf[1]
এর মধ্যে তুলনা করে দেখতে পাই যে আমাদের array[k]
তে highHalf[1]
কপি করতে হবে। এরপর আমরা k
ও j
কে বৃদ্ধি করি:এভাবেই চলবে, সবসময়
lowHalf[i]
ও highHalf[j]
এর মধ্যে তুলনা করব, ক্ষুদ্রতর মানটিকে array[k]
তে কপি করব এবং হয় i
অথবা j
বৃদ্ধি করব:পরিশেষে, হয়
lowHalf
এর সবগুলো বা highHalf
এর সবগুলো array
তে কপি হবে। এই উদাহরনে, highHalf
সবগুলো উপাদান lowHalf
এর বেশকিছু উপাদানের আগেই কপি হয়ে গেছে। সবশেষে আমরা lowHalf
বা highHalf
এর বাকি মানগুলো কপি করে নিব:আমরা বলেছিলাম যে সংখ্যক উপাদানকে একত্রকরণ করতে সময় লাগবে, আর তাই একত্রকরণ সময়কাল সাবঅ্যারে আকারের সাথে সরলরৈখিক। চল দেখি এটা কেন সত্য। আমরা একত্রকরণের তিনটে ধাপ দেখেছি:
- Copy each element in
array[p..r]
into eitherlowHalf
orhighHalf
. - As long as some elements are untaken in both
lowHalf
andhighHalf
, compare the first two untaken elements and copy the smaller one back intoarray
. - Once either
lowHalf
orhighHalf
has had all its elements copied back intoarray
, copy each remaining untaken element from the other temporary array back intoarray
.
এই প্রত্যেকটি ধাপের জন্য আমাদের কত লাইন কোড করা লাগবে? প্রতিটি উপাদানের জন্য এটা ধ্রুব সংখ্যা। প্রথম ধাপে সংখ্যক উপাদান আছে, একত্রকরণের সময়কাল প্রকৃতপক্ষেই হচ্ছে ।
array
থেকে প্রতিটি উপাদান হয় lowHalf
বা highHalf
একবারই কপি করা হয়েছে। দ্বিতীয় ধাপে প্রত্যেকটি তুলনার সময় ধ্রুবক, যেহেতু এখানে শুধু দুইটি উপাদানের তুলনা করা হয়েছে এবং প্রত্যেকটি উপাদান একবার তুলনাতেই "পাওয়া" যায়। দ্বিতীয় ও তৃতীয় ধাপ মিলিয়ে প্রত্যেকটি উপাদান আবার array
তে একবারই কপি করা হয়েছে। যেহেতু আমরা প্রতিটি উপাদানের জন্য প্রতি লাইন কোড ধ্রুব সংখ্যক বার চালাব এবং আমরা ধরে নিচ্ছি সাবঅ্যারে array[p..q]
তে 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 দিয়ে লাইসেন্সকৃত।
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।