यथा-स्थान दो सरणियों

Question

के मर्ज हम क्रमबद्ध क्रम में आकार m + n की एक सरणी जिसमें मीटर तत्वों, मौजूद हैं क्रमबद्ध क्रम में, और आकार n की एक दूसरी सरणी, फिर से की है। हम चाहते हैं कि वे दोनों को पहले सरणी में सॉर्ट और प्रस्तुत किया जाए। कोई तीसरा सरणी दिया जाना चाहिए।

उदाहरण:

1, 3, 55, 66, 77, _, _, _ 
    5, 9, 20 

जवाब होगा:

1, 3, 5, 9, 20, 55, 66, 77 

Answer 1

एक नियमित विलय प्रकार करें लेकिन पहले सबसे बड़ी संख्या की तुलना में विपरीत में, पहले सरणी के अंत में पीछे (पीछे की ओर) संग्रहित करें। इस तरह, जिन तत्वों को आप विलय कर रहे हैं वे कभी भी ओवरराइट नहीं होते हैं (यह कि यह काम आसान है कि आप एक पल के लिए इसके बारे में सोचते हैं)।

Answer 2

पहली सरणी के अंत में पहली सरणी की सामग्री को ले जाएँ, ऐसा है कि खाली तत्वों शुरुआत में अब कर रहे हैं । फिर पहले अनुक्रम में सामान्य रूप से दो अनुक्रमों को मर्ज करें।

Answer 3

जगह में मूल रूप से आवश्यकता है कि हम केवल "निरंतर" स्मृति का उपयोग करें, जो विभिन्न इनपुट सरणी आकारों के साथ नहीं बदलता है। हालांकि, सवाल स्वयं अतिरिक्त मात्रा में स्मृति आवंटित करता है जो दो इनपुट एरे में से एक के आकार के समान होता है, जो ओ (एन) स्मृति सबसे बुरी स्थिति में है। यह मूल रूप से करने के विचार में आता है "यथा-स्थान" अर्थहीन ...

सवाल बेहतर "अतिरिक्त स्मृति के बिना मर्ज" है, जो अपने असली इरादे के बारे में एक और अधिक सटीक वर्णन है के रूप में phrased जा सकती है ...

Answer 4

// merge the elements in B[] to A[], starting from the last one 
    void merge(int A[], int m, int B[], int n) { 
     // m-1 and n-1 represent the current element index in A[] and B[] respectively 
     while (n > 0) { // there are still elements in B[] not merged 
      if (m > 0 && A[m-1] > B[n-1]) { // current element in A[] > current element in B[] 
      A[m+n-1] = A[m-1]; // move current element of A[] to its right position 
      --m; // decrease current element index of A[] 
      } 
     else { // current element in A[] <= current element in B[] 
      A[m+n-1] = B[n-1]; // move current element in B[] to its right position 
      --n; // decrease current element index of B[] 
     } 
     } 
    }