ডেটা স্ট্রাকচারে অ্যালগরিদম মার্জ করুন

মার্জ অ্যালগরিদম দুটি সাজানো তালিকাকে একটি তালিকায় একত্রিত করতে ব্যবহৃত হয়। এই অ্যালগরিদম বিভিন্ন ক্ষেত্রে ব্যবহার করা হয়। আমরা যদি মার্জ সর্ট করতে চাই, তাহলে আমাদের বাছাই তালিকাগুলিকে আরও বড় তালিকায় মার্জ করতে হবে৷

পদ্ধতি সহজ. আমরা দুটি তালিকা নিই, দুটি পয়েন্টার থাকবে। প্রথমটি মুষ্টি তালিকার উপাদানগুলির দিকে নির্দেশ করবে, দ্বিতীয়টি দ্বিতীয় তালিকার উপাদানগুলির দিকে নির্দেশ করবে৷ তাদের মানের উপর ভিত্তি করে, এই দুটি তালিকার একটি থেকে ছোট উপাদান নেওয়া হয়, তারপর সেই সংশ্লিষ্ট তালিকার পয়েন্টার বাড়ান। একটি তালিকা শেষ না হওয়া পর্যন্ত এই অপারেশনটি করা হবে। তারপরে চূড়ান্ত একত্রিত তালিকার শেষে অবশিষ্ট তালিকা যোগ করুন।

আসুন আরও ভাল ধারণা পেতে দৃষ্টান্তটি দেখি।

অ্যালগরিদম

মার্জ (অ্যারে, বাম, মধ্য, ডান) -

Begin
   nLeft := m - left+1
   nRight := right – m
   define arrays leftArr and rightArr of size nLeft and nRight respectively
   for i := 0 to nLeft do
      leftArr[i] := array[left +1]
   done
   for j := 0 to nRight do
      rightArr[j] := array[middle + j +1]
   done
   i := 0, j := 0, k := left
   while i < nLeft AND j < nRight do
      if leftArr[i] <= rightArr[j] then
         array[k] = leftArr[i]
         i := i+1
      else
         array[k] = rightArr[j]
         j := j+1
         k := k+1
      done
   while i < nLeft do
      array[k] := leftArr[i]
      i := i+1
      k := k+1
   done
   while j < nRight do
      array[k] := rightArr[j]
      j := j+1
      k := k+1
   done
End