एक क्रमपरिवर्तन खोजें जो सी ++ में मर्ज सॉर्ट के सबसे खराब मामले का कारण बनता है

मान लीजिए हमारे पास तत्वों का एक सेट है; हमें यह पता लगाना होगा कि इन तत्वों के किस क्रमपरिवर्तन के परिणामस्वरूप मर्ज सॉर्ट की सबसे खराब स्थिति होगी? जैसा कि हम असम्बद्ध रूप से जानते हैं, मर्ज सॉर्ट हमेशा 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 से बढ़ाएँ), −
  करें
  • गिरफ्तारी[i] :=बाएं[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