Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> सी प्रोग्रामिंग

एक क्रमपरिवर्तन खोजें जो 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

विधि

हम जांच करते हैं कि इनपुट सेट के लिए मर्ज सॉर्ट के लिए सबसे खराब स्थिति इनपुट कैसे प्राप्त करें?

अब हम एरे को बॉटम अप तरीके से बनाने की कोशिश करते हैं

अब क्रमबद्ध सरणी {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} की होगी।

पूर्ण एल्गोरिथम

WorstCase उत्पन्न करें (गिरफ्तारी [])

  • अब हम बाएँ और दाएँ दो सहायक सरणियाँ बनाते हैं और उनमें वैकल्पिक सरणी तत्व संग्रहीत करते हैं।

  • हम GenerateWorstCase को लेफ्ट सबअरे के लिए कहते हैं - GenerateWorstCase (बाएं)

  • हम GenerateWorstCase को राइट सबएरे GenerateWorstCase (दाएँ) के लिए कहते हैं

  • अब हम बाएँ और दाएँ उप-सरणी के सभी तत्वों को मूल सरणी में कॉपी करते हैं।

उदाहरण

// C program to generate Worst Case of Merge Sort
#include <stdlib.h>
#include <stdio.h>
// Indicates function to print an array
void printArray(int A1[], int size1){
   for (int i = 0; i < size1; i++)
      printf("%d ", A1[i]);
   printf("\n");
}
// Indicates function to join left and right subarray
int join(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
   int i; // So used in second loop
   for (i = 0; i <= m1 - l1; i++)
      arr1[i] = left1[i];
   for (int j = 0; j < r1 - m1; j++)
      arr1[i + j] = right1[j];
}
// Indicates function to store alternate elemets in left
// and right subarray
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];
}
// Indicates function to generate Worst Case of Merge Sort
int generateWorstCase(int arr1[], int l1, int r1){
   if (l1 < r1){
      int m1 = l1 + (r1 - l1) / 2;
      // creating two auxillary arrays
      int left1[m1 - l1 + 1];
      int right1[r1 - m1];
      // Storing alternate array elements in left
      // and right subarray
      split(arr1, left1, right1, l1, m1, r1);
      // Recursing first and second halves
      generateWorstCase(left1, l1, m1);
      generateWorstCase(right1, m1 + 1, r1);
      // joining left and right subarray
      join(arr1, left1, right1, l1, m1, r1);
   }
}
// Driver code
int main(){
   // Initializes sorted array
   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("Sorted array is \n");
   printArray(arr1, n1);
   // generating worst Case of Merge Sort
   generateWorstCase(arr1, 0, n1 - 1);
   printf("\nInput array that will result in " "worst case of merge sort is \n");
   printArray(arr1, n1);
   return 0;
}

आउटपुट

Sorted array is
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Input array that will result in worst case of merge sort is
11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26

  1. सी प्रोग्राम मर्ज सॉर्ट का उपयोग करके एक सरणी को सॉर्ट करने के लिए

    एक सरणी संबंधित डेटा आइटम का एक समूह है जो एक सामान्य नाम साझा करता है। किसी सरणी में किसी विशेष मान की पहचान उसके इंडेक्स नंबर की सहायता से की जाती है। सरणी घोषित करना एक सरणी घोषित करने के लिए वाक्य रचना इस प्रकार है - datatype array_name [size]; उदाहरण के लिए, float marks [50] यह 50 फ्लोट तत्व

  1. सी प्रोग्राम फॉर इटरेटिव मर्ज सॉर्ट

    मर्ज सॉर्ट करें जो डिवाइड और जीत तकनीक के आधार पर एक सॉर्टिंग एल्गोरिदम है। मर्ज सॉर्ट की समय जटिलता ओ (एन लॉग एन) है। एल्गोरिथ्म पहले सरणी को बराबर हिस्सों में विभाजित करता है और फिर उन्हें एक निश्चित तरीके से मिला देता है। इटरेटिव मर्ज सॉर्ट पुनरावृत्त मर्ज सॉर्ट में, हम पुनरावर्ती दृष्टिकोण का उ

  1. सी/सी++ प्रोग्राम मर्ज सॉर्ट का उपयोग करके एक सरणी में व्युत्क्रमों की गणना करने के लिए?

    दिए गए सरणी को क्रमबद्ध करने के लिए होने वाले व्युत्क्रमों की संख्या को व्युत्क्रम गणना के रूप में जाना जाता है। उलटा समस्या एक शास्त्रीय समस्या है जिसे मर्ज सॉर्ट एल्गोरिदम का उपयोग करके हल किया जा सकता है। इस समस्या में हम इसके बाईं ओर सभी तत्वों को अधिक से अधिक गिनेंगे और गिनती को आउटपुट में जोड़