अवधारणा
तत्वों के दिए गए सेट के संबंध में, निर्धारित करें कि इन तत्वों का कौन सा क्रमपरिवर्तन मर्ज सॉर्ट के सबसे खराब मामले का परिणाम देगा?
हम जानते हैं, स्पर्शोन्मुख रूप से, मर्ज सॉर्ट हमेशा 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
विधि
हम जांचते हैं कि किसी इनपुट सेट के लिए मर्ज सॉर्ट के सबसे खराब मामले का इनपुट कैसे प्राप्त करें?
अब हम नीचे-ऊपर के तरीके से सरणी बनाने का प्रयास करते हैं।
अब मान लीजिए सॉर्ट की गई सरणी {11, 12, 13, 14, 15, 16, 17, 18} है।
अब मर्ज सॉर्ट के सबसे खराब मामले को बनाने के लिए, मर्ज ऑपरेशन जिसके परिणामस्वरूप उपरोक्त सॉर्ट की गई सरणी बनी है, उसमें सबसे बड़ी तुलनाएं होनी चाहिए। इसके परिणामस्वरूप, मर्ज ऑपरेशन में शामिल बाएं और दाएं उप-सरणी को सॉर्ट की गई सरणी के वैकल्पिक तत्वों को संग्रहीत करना चाहिए जैसे कि, बाएं उप-सरणी {11, 13, 15, 17} होनी चाहिए और दाएं उप-सरणी {12, 14, 16, 18} होनी चाहिए। इसलिए सरणी के प्रत्येक तत्व की तुलना कम से कम एक बार की जाएगी और इससे अधिकतम तुलनाएं होंगी। अब हम बाएं और दाएं उप-सरणी के लिए समान तर्क लागू करते हैं। सरणी {11, 13, 15, 17} के संबंध में, सबसे खराब मामला तब होगा जब इसके बाएं और दाएं उप-सरणी {11, 15} और {13, 17} होंगे और सरणी {12, 14, 16, 18} के लिए सबसे खराब मामला {12, 14} और {16, 18} के लिए होगा।
पूर्ण एल्गोरिदम
GenerateWorstCase(arr[])
अब हम दो सहायक सरणी left और right बनाते हैं और उनमें वैकल्पिक सरणी तत्वों को संग्रहीत करते हैं।
हम बाएं उप-सरणी के लिए GenerateWorstCase कॉल करते हैं - GenerateWorstCase(left)
हम दाएं उप-सरणी के लिए GenerateWorstCase कॉल करते हैं - GenerateWorstCase(right)
अब हम बाएं और दाएं उप-सरणी के सभी तत्वों को मूल सरणी में वापस कॉपी करते हैं।
उदाहरण
// C प्रोग्राम मर्ज सॉर्ट के सबसे खराब मामले को उत्पन्न करने के लिए #include <stdlib.h> #include <stdio.h> // सरणी प्रिंट करने वाला फ़ंक्शन void printArray(int A1[], int size1){ for (int i = 0; i < size1; i++) printf("%d ", A1[i]); printf("\n"); } // बाएं और दाएं उप-सरणी को जोड़ने वाला फ़ंक्शन int join(int arr1[], int left1[], int right1[], int l1, int m1, int r1){ int i; // दूसरे लूप में उपयोग के लिए for (i = 0; i <= m1 - l1; i++) arr1[i] = left1[i]; for (int j = 0; j < r1 - m1; j++) arr1[i + j] = right1[j]; } // बाएं और दाएं उप-सरणी में वैकल्पिक तत्वों को संग्रहीत करने वाला फ़ंक्शन int split(int arr1[], int left1[], int right1[], int l1, int m1, int r1){ for (int i = 0; i <= m1 - l1; i++) left1[i] = arr1[i * 2]; for (int i = 0; i < r1 - m1; i++) right1[i] = arr1[i * 2 + 1]; } // मर्ज सॉर्ट के सबसे खराब मामले को उत्पन्न करने वाला फ़ंक्शन int generateWorstCase(int arr1[], int l1, int r1){ if (l1 < r1){ int m1 = l1 + (r1 - l1) / 2; // दो सहायक सरणी बनाना int left1[m1 - l1 + 1]; int right1[r1 - m1]; // सरणी के वैकल्पिक तत्वों को बाएं // और दाएं उप-सरणी में संग्रहीत करना split(arr1, left1, right1, l1, m1, r1); // पहले और दूसरे आधे भाग पर पुनरावृत्ति generateWorstCase(left1, l1, m1); generateWorstCase(right1, m1 + 1, r1); // बाएं और दाएं उप-सरणी को जोड़ना join(arr1, left1, right1, l1, m1, r1); } } // ड्राइवर कोड int main(){ // सॉर्ट की गई सरणी प्रारंभ करें int arr1[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 }; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("सॉर्ट की गई सरणी है \n"); printArray(arr1, n1); // मर्ज सॉर्ट का सबसे खराब मामला उत्पन्न करना generateWorstCase(arr1, 0, n1 - 1); printf("\nइनपुट सरणी जो परिणाम देगी " "मर्ज सॉर्ट का सबसे खराब मामला \n"); printArray(arr1, n1); return 0; } आउटपुट
सॉर्ट की गई सरणी है 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
