अतिरिक्त मेमोरी का उपयोग किए बिना मर्ज करें

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

लेकिन मैंने फिर भी कोशिश करने का फैसला किया।

लीनियर मर्ज

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

• नंबर चुनें S≈sqrt (N)
• सरणी को लंबाई एस के टुकड़ों में विभाजित करें । शेष, जो किसी भी टुकड़े में नहीं गिरा, जब तक हम स्पर्श नहीं करते
• वह टुकड़ा जिसमें गिरे हुए टुकड़ों के बीच की सीमा को अंतिम टुकड़े के साथ बदल दिया जाता है। यह हमारा क्लिपबोर्ड होगा।
• हम पहले तत्वों के आरोही क्रम में शेष भाग K-1 को सॉर्ट करते हैं। यहां हमें एक एल्गोरिथ्म का उपयोग करने की आवश्यकता है जो एक्सचेंजों की संख्या में रैखिक है। न्यूनतम तत्व का चयन करके छाँटना उपयुक्त है।
• हम दो महत्वपूर्ण बातों पर ध्यान देते हैं। सबसे पहले, यदि हमारे पास लंबाई ए और बी में सॉर्ट किए गए टुकड़े के दो आदेश हैं और एक क्लिपबोर्ड जिसकी लंबाई मिनट (ए, बी) से कम नहीं है, तो हम ए + बी तुलना और ए + बी से अधिक नहीं खर्च करके इन टुकड़ों को मिला सकते हैं । + मिनट (ए, बी) एक्सचेंज। क्लिपबोर्ड में आइटम का क्रम बदल सकता है। दूसरे, जब (के -1) * एस तत्वों से पिछले चरण में प्राप्त सरणी को सॉर्ट करते हैं, तो प्रत्येक तत्व एस पदों से अधिक नहीं छोड़ सकता है, अर्थात्। पिछले "टुकड़ा" के बाईं ओर कभी नहीं होगा।
• क्लिपबोर्ड का उपयोग करते हुए, हम क्रमिक रूप से पड़ोसी टुकड़ों के जोड़े को मिलाते हैं - [0..S-1] और [S, 2 * S-1] , फिर [S, 2 * S-1] और [2 * S, 3 * S-1। ] इत्यादि। पिछले पैराग्राफ से यह इस प्रकार है कि परिणामस्वरूप हमें M = S * (K-1) तत्वों का एक सॉर्ट किया गया सरणी मिलता है
• हम किसी भी एल्गोरिथ्म द्वारा मूल सरणी के अंतिम आर = एनएम तत्व (क्लिपबोर्ड + शेष) को सॉर्ट करते हैं। वे किसी तरह के द्विघात एल्गोरिथ्म (विचार की शुद्धता के लिए, पुनरावृत्ति से बचने के लिए) की सलाह देते हैं, लेकिन व्यावहारिक दृष्टिकोण से, सॉर्ट करने के लिए पुनरावर्ती कॉल कोई बदतर नहीं है।
• सरणी के सॉर्ट किए गए अंशों को जोड़ना [R..NR-1] और [NR..N-1] टुकड़े के रूप में [0..R-1] क्लिपबोर्ड के रूप में उपयोग करना
• हम एल्गोरिथ्म में एक त्रुटि के लिए पिछले और अगले पैराग्राफ के जंक्शन को देख रहे हैं। यदि आपको यह नहीं मिलता है, तो यह लेख के अंत में समझाया गया है।
• हम क्लिपबोर्ड को सॉर्ट करते हैं: इसमें सम्‍मिलित हैं और आर के लघु तत्व बने हुए हैं, और सॉर्ट करने के बाद वे जगह में होंगे

वर्णन काफी लंबा है, लेकिन आप समझ सकते हैं। एक विलय के लिए एक्सचेंजों की संख्या लगभग 5 * एन है , तुलनाओं की संख्या लगभग 6 * एन है (यह अवशेषों की लंबाई पर निर्भर करता है)। पूर्ण छँटाई के लिए, इन संख्याओं को लॉग (एन) से गुणा किया जाता है, और बहुत कुछ प्राप्त होता है।

छँटाई के लिए एल्गोरिथ्म अनुकूलन

हमारे लिए इसे आसान बनाने के लिए, और अधिक कुशलता से काम करने के लिए एल्गोरिथ्म, हम निम्नलिखित नोट करते हैं।

• क्लिपबोर्ड के साथ सभी उपद्रव और सरणी के साथ इसके बाद के विलय की आवश्यकता है केवल अगर सरणी में वास्तव में खाली स्थान नहीं था। यदि हम लंबाई ए और बी के टुकड़ों को मर्ज करते हैं, और उनके बाद कम से कम अनसोल्ड स्पेस की सेल हैं, तो यह हमारे लिए सरणियों को टुकड़ों में विभाजित करने, उन्हें सॉर्ट करने और मर्ज करने के लिए पर्याप्त है। यह विशेष रूप से प्रभावी ढंग से काम करेगा अगर S = A = B।
• हमें यह सुनिश्चित करने की कोशिश करनी चाहिए कि शेष की लंबाई शून्य है, और सॉर्ट किए गए टुकड़ों के बीच की सीमा एस के टुकड़ों के बॉर्डर पर बिल्कुल गिरती है । इसे प्राप्त करने का सबसे आसान तरीका यह है कि एस को दो की शक्ति के बराबर चुनें, और ए और बी को इसके द्वारा विभाजित करें।
• सरणियों के छंटाई के टुकड़ों की आवश्यकता होती है ((ए + बी) / एस) 2/2 तुलना। बाद में क्लिपबोर्ड की छँटाई - ओ (एस * लॉग (एस)) तुलना। इसलिए, sqrt (N) के करीब S चुनना आवश्यक नहीं है; आप इसे बढ़ा सकते हैं, उदाहरण के लिए, N / log (N) के लिए ।

इन विचारों के साथ सशस्त्र, हम एक कार्यक्रम लिख रहे हैं (अब तक केवल प्रकार के एक सरणी int [] के लिए)। सबसे पहले, हम टुकड़ों को दो की शक्ति के बराबर लंबाई के साथ सॉर्ट और मर्ज करते हैं, और हम कड़ाई से बाएं से दाएं जाते हैं ताकि दाएं से मुक्त स्थान हो। जब हम क्लिपबोर्ड पर आते हैं, तो अप्रयुक्त, लेकिन सॉर्ट किए गए टुकड़े मर्ज करते हैं। हम क्लिपबोर्ड + शेष को सॉर्ट करते हैं, परिणाम को बाकी सरणी के साथ मर्ज करते हैं, नए बनाए गए क्लिपबोर्ड को सॉर्ट करते हैं - और सरणी को सॉर्ट किया जाता है। यह लगभग सौ लाइनों का एक एल्गोरिथ्म बताता है । सच कहा गया था भारी। दक्षता के बारे में क्या?

ईमानदारी से, मैं उम्मीद कर रहा था कि वह मानक qsort से 3 बार से अधिक खो देगा। लेकिन वास्तविक स्थितियों में तुलना (10 ⁸ लंबे तक सरणियों पर) ने दिखाया कि qsort एल्गोरिदम तुलनात्मक संख्या में लगभग 10% है, और कुल परिचालन समय में 1.2 से 1.3 गुना है! शायद यह इस तथ्य के कारण है कि आईसीएमपी फ़ंक्शन (दिए गए पते पर दो पूर्णांक की तुलना) को इनलाइन प्रतिस्थापित किया जाता है - लेकिन जो कोड डाला जाता है वह बहुत भयानक हो जाता है (मैंने जाँच की)।

सामान्य तौर पर, सब कुछ उतना बुरा नहीं है जितना उन्होंने कहा था।

लेकिन एल्गोरिथम के वर्णन में किस तरह की त्रुटि थी? तथ्य यह है कि अगर कोई तत्व क्लिपबोर्ड पर या शेष पर पहुंच जाता है, जो छंटाई के बाद पहले आर पदों में से एक में होना चाहिए, तो अंत में यह जगह में नहीं मिलेगा। इसे ठीक करने के लिए, आपको ट्रैक रखना होगा कि इंडेक्स आर के साथ सेल में जो तत्व था, वह पिछले मर्ज में गिर गया और अंतिम टुकड़ा को इस स्थान पर प्रारंभिक सॉर्ट करना है (इसकी लंबाई R से थोड़ी लंबी हो सकती है)।

UPD: एल्गोरिथ्म में, जैसा कि मैंने यहां बताया, "सरणी के टुकड़ों को छाँटने" से संबंधित एक और त्रुटि का पता चला। यदि स्रोत सरणी में कई समान तत्व हैं, तो सरणी के एक ही टुकड़े से अलग टुकड़ों में समान तत्व हो सकते हैं। और यदि क्रम जिसमें ये टुकड़े जाते हैं, छँटाई के दौरान उल्लंघन किया जाएगा, तो पूरे सरणी को छाँटने का परिणाम गलत हो सकता है।

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