मान लीजिए हमारे पास तत्वों का एक सेट है; हमें यह ढूंढना है कि इन तत्वों का कौन सा क्रमचय मर्ज सॉर्ट की सबसे खराब स्थिति का कारण बनेगा? जैसा कि हम जानते हैं कि एसिम्प्टोटिकली, मर्ज सॉर्ट हमेशा 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] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक फंक्शन merge() परिभाषित करें, जो सरणी arr, सरणी left, सरणी right, l_index, m_index, r_index लेगा,
- i := 0 से आरंभ करें, जब i <= m_index - l_index, अपडेट करें (i को 1 से बढ़ाएं), करें -
- arr[i] := left[i]
- j := 0 से आरंभ करें, जब j < r_index - m_index, अपडेट करें (j को 1 से बढ़ाएं), करें -
- arr[i + j] = right[j]
- एक फंक्शन divide() परिभाषित करें, जो सरणी arr, सरणी left, सरणी right, l_index, m_index, r_index लेगा,
- i := 0 से आरंभ करें, जब i <= m_index - l_index, अपडेट करें (i को 1 से बढ़ाएं), करें -
- left[i] := arr[i * 2]
- i := 0 से आरंभ करें, जब i < r_index - m_index, अपडेट करें (i को 1 से बढ़ाएं), करें -
- right[i] := arr[i * 2 + 1]
- एक फंक्शन gen_worst_seq() परिभाषित करें, जो सरणी arr[], l_index, r_index लेगा,
- यदि l_index < r_index, तो -
- m_index := l_index + (r_index - l_index) / 2
- आकार m_index-l_index+1 की सरणी left परिभाषित करें।
- आकार r_index-m_index की सरणी right परिभाषित करें।
- 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)
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#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
