C++ এ মার্জ সর্টের সবচেয়ে খারাপ কেস সৃষ্টি করে এমন একটি স্থানচ্যুতি খুঁজুন

ধরুন আমাদের কিছু উপাদান আছে; আমাদের খুঁজে বের করতে হবে এই উপাদানগুলির কোন স্থানান্তরের ফলে মার্জ সর্টের সবচেয়ে খারাপ অবস্থা হবে? আমরা যেমন অসংগতভাবে জানি, মার্জ সর্ট সর্বদা O (n log n) সময় ব্যয় করে, তবে কিছু ক্ষেত্রে আরও তুলনার প্রয়োজন হয় এবং আরও সময় ব্যয় করে। এখানে আমাদের ইনপুট উপাদানগুলির একটি পারমুটেশন খুঁজে বের করতে হবে যেগুলির জন্য একটি সাধারণ মার্জ সর্ট অ্যালগরিদম প্রয়োগ করার সময় বাছাই করার সময় তুলনার উচ্চ সংখ্যক প্রয়োজন হবে৷

সুতরাং, যদি ইনপুটটি [11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26] এর মত হয়, তাহলে আউটপুট হবে [11,19] ,15,23,13,21,17,25,12,20,16,24,14,22,18,26]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন মার্জ(), এটি অ্যারে অ্যারে, অ্যারে বাম, অ্যারে ডান, l_index, m_index, r_index,
নেবে।
• আরম্ভ করার জন্য i :=0, যখন i <=m_index - l_index, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), করুন −
  • arr[i] :=left[i]
• আরম্ভ করার জন্য j :=0, যখন j
• arr[i + j] =right[j]

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
void display(int A[], int size) {
   for (int i = 0; i < size; i++)
      cout << A[i] << " ";
   cout << endl;
}
int merge(int arr[], int left[], int right[],int l_index, int m_index, int r_index) {
   int i;
   for (i = 0; i <= m_index - l_index; i++)
      arr[i] = left[i];
   for (int j = 0; j < r_index - m_index; j++)
      arr[i + j] = right[j];
}
int divide(int arr[], int left[], int right[], int l_index, int m_index, int r_index) {
   for (int i = 0; i <= m_index - l_index; i++)
      left[i] = arr[i * 2];
   for (int i = 0; i < r_index - m_index; i++)
      right[i] = arr[i * 2 + 1];
}
int gen_worst_seq(int arr[], int l_index, int r_index) {
   if (l_index < r_index) {
      int m_index = l_index + (r_index - l_index) / 2;
      int left[m_index - l_index + 1];
      int right[r_index - m_index];
      divide(arr, left, right, l_index, m_index, r_index);
      gen_worst_seq(left, l_index, m_index);
      gen_worst_seq(right, m_index + 1, r_index);
      merge(arr, left, right, l_index, m_index, r_index);
   }
}
int main() {
   int arr[] = {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
   int n = sizeof(arr) / sizeof(arr[0]);
   gen_worst_seq(arr, 0, n - 1);
   display(arr, n);
}

ইনপুট

11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26

আউটপুট

11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26