एक सरणी

Question

में जगह में विलय के संबंध में मैं निम्नलिखित प्रश्न में आया था।

n तत्वों की एक सरणी और एक पूर्णांक कश्मीर जहां कश्मीर < n को देखते हुए। तत्वों {एक ... एक _{कश्मीर}} और {एक _{कश्मीर +1} ... एक_n} पहले से ही हल कर रहे हैं। ओ (एन) समय और ओ (1) स्थान में क्रमबद्ध करने के लिए एक एल्गोरिदम दें।

ऐसा लगता है कि यह ओ (एन) समय और ओ (1) स्थान में किया जा सकता है। वास्तव में समस्या यह पूछ रही है कि विलय के मर्ज चरण को कैसे करें और जगह में कैसे करें। यदि यह संभव था, तो विलय को इस तरह लागू नहीं किया जाएगा? मैं खुद को मनाने में असमर्थ हूं और कुछ राय चाहिए।

Answer 1

This संकेत मिलता है कि यह ओ (एलजी^2 एन) अंतरिक्ष में ऐसा करना संभव है लगता है। मैं यह नहीं देख सकता कि कैसे साबित करना है कि निरंतर स्थान में विलय करना असंभव है, लेकिन मैं नहीं देख सकता कि इसे कैसे किया जाए।

संपादित करें: पीछा संदर्भ, नुथ खंड 3 - व्यायाम 5.5.3 कहते हैं, "एल Trabb-पार्डो का एक काफी अधिक जटिल एल्गोरिथ्म इस समस्या का सबसे अच्छा संभव उत्तर प्रदान करता है: यह हे में स्थिर विलय करना संभव है (एन) ओ (एन एलजी एन) समय में समय और स्थिर सॉर्टिंग, सूचकांक चर के एक निश्चित संख्या के लिए सहायक स्मृति के केवल ओ (एलजी एन) बिट्स का उपयोग करते हुए

अधिक references जो मैंने पढ़ा नहीं है। दिलचस्प के लिए धन्यवाद समस्या

आगे संपादित करें: यह आलेख दावा करता है कि हुआंग और लैंगस्टन के आलेख में एक एल्गोरिदम है जो समय में आकार एम और एन की दो सूचियों को विलय करता है ओ (एम + एन), तो आपके प्रश्न का उत्तर हाँ प्रतीत होता है। दुर्भाग्य से मेरे पास इस आलेख तक पहुंच नहीं है, इसलिए मुझे दूसरी हाथ की जानकारी पर भरोसा करना चाहिए। मुझे यकीन नहीं है कि नाउथ की घोषणा के साथ इसे कैसे सुलझाना है कि ट्रेब-पार्डो एल्गोरिदम इष्टतम है। अगर मेरा जीवन इस पर निर्भर करता है, तो मैं Knuth के साथ जाऊंगा।

अब मैं देखता हूं कि इसे पहले और पहले स्टैक ओवरफ़्लो questionnumber से पूछा गया था। मेरे पास डुप्लिकेट के रूप में इसे ध्वजांकित करने का दिल नहीं है।

हुआंग बी.- सी। और लैंगस्टन एम। ए, प्रैक्टिकल इन-प्लेस विलय, कॉम। एसीएम 31 (1 9 88) 348-352

Answer 2

नहीं, यह संभव नहीं है, हालांकि यह मेरा काम बहुत आसान होगा :)।

आपके पास एक ओ (लॉग एन) कारक है जिसे आप टालना नहीं कर सकते हैं। आप इसे समय या स्थान के रूप में लेना चुन सकते हैं, लेकिन इससे बचने का एकमात्र तरीका सॉर्ट नहीं करना है। ओ (लॉग एन) स्पेस के साथ आप निरंतरता की एक सूची बना सकते हैं जो ट्रैक रखती है कि आपने उन तत्वों को कैसे रखा है जो काफी फिट नहीं थे। रिकर्सन के साथ इसे ओ (1) ढेर में फिट करने के लिए बनाया जा सकता है, लेकिन यह केवल ओ (लॉग एन) स्टैक फ्रेम का उपयोग करके किया जा सकता है।

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

 
.  - 
135792468 
. - 
135792468 
    : .- 
125793468 
    : .- 
123795468 
    #.:- 
123495768 
    :.- 
123459768 
     .:- 
123456798 
     .- 
123456789 

123456789 

कुछ नाजुक सीमा की स्थिति, द्विआधारी खोज की तुलना में थोड़ा कठिन सही पाने के लिए, और यहां तक ​​कि इस (संभव) के रूप में है, और इसलिए एक बुरा होमवर्क समस्या नहीं है; लेकिन वास्तव में एक अच्छा मानसिक अभ्यास।

अद्यतन जाहिर है मैं गलत हूँ और वहाँ एक एल्गोरिथ्म है कि हे (एन) समय और हे (1) स्थान प्रदान करता है। मैंने खुद को प्रबुद्ध करने के लिए कागजात डाउनलोड किए हैं, और इस उत्तर को गलत के रूप में वापस ले लिया है।

Answer 3

ऐसा करने के लिए कई एल्गोरिदम हैं, जिनमें से कोई भी अंतर्ज्ञान करने में बहुत आसान नहीं है। मुख्य विचार है कि बफर के रूप में विलय करने के लिए सरणी के एक हिस्से का उपयोग करना, फिर सहायक अंतरिक्ष के लिए इस बफर का उपयोग करके मानक विलय करना। यदि आप तत्वों को फिर से बदल सकते हैं ताकि बफर तत्व सही जगह पर हों, तो आप सुनहरे हो।

यदि आपने इसे देखने में रुचि रखते हैं तो मैंने अपनी व्यक्तिगत साइट पर इन एल्गोरिदम में से an implementation लिखा है। यह हुआंग और लैंगस्टन द्वारा "प्रैक्टिकल इन-प्लेस विलय" पेपर पर आधारित है। आप शायद कुछ अंतर्दृष्टि के लिए उस पेपर को देखना चाहेंगे।

मैंने यह भी सुना है कि इसके लिए अच्छे अनुकूली एल्गोरिदम हैं, जो आपके चयन के कुछ निश्चित आकार के बफर का उपयोग करते हैं (जो ओ (1) हो सकता है यदि आप चाहते थे), लेकिन फिर बफर आकार के साथ सुन्दरता से स्केल करें। मुझे इनमें से कोई भी मेरे सिर के ऊपर से नहीं जानता है, लेकिन मुझे यकीन है कि "अनुकूली विलय" की त्वरित खोज कुछ हो सकती है।