तेज, किफायती, टिकाऊ ...

यदि आपको एक सरणी छँटाई एल्गोरिथ्म की आवश्यकता है जो:

• ओ (एन * लॉग (एन)) संचालन (एक्सचेंज और तुलना) के लिए गारंटीकृत काम करेगा;
• ओ (1) अतिरिक्त मेमोरी की आवश्यकता होगी;
• यह स्थिर होगा (अर्थात, यह एक ही कुंजी के साथ तत्वों के क्रम को नहीं बदलता है)

तब आपको इन तीन में से किसी भी दो बिंदु तक खुद को सीमित रखने की पेशकश की जाएगी। और, अपनी पसंद के आधार पर, आपको, उदाहरण के लिए, या तो मर्ज सॉर्ट (ओ (एन) अतिरिक्त मेमोरी की आवश्यकता होती है), या पिरामिडल सॉर्ट (अस्थिर), या बबल सॉर्ट (ओ (एन ^{2 के} लिए काम करता है)) मिलेगा। यदि आप O (लॉग (N)) ("पुनरावर्तन के लिए") के लिए मेमोरी आवश्यकता को कमज़ोर कर देते हैं, तो आपके लिए जटिलता O (N * (log (N) ² )) के साथ एक एल्गोरिथ्म है - बल्कि बहुत कम ज्ञात है, हालांकि यह इसका संस्करण है जिसे कार्यान्वयन में उपयोग किया जाता है विधि एसटीडी :: static_sort ()।

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


लेखकों का कहना है कि उनका एल्गोरिथ्म पहले नहीं है, और 1974 के एल स्पेसबर्डो, स्थिर छँटाई और समय सीमा के साथ विलय के काम को देखें। यह स्कैन किए गए पाठ के लगभग 80 पृष्ठ हैं, और मैंने इसका पता लगाने की कोशिश नहीं की।

मुझे उन लोगों के लिए तुरंत कहना चाहिए, जो हुआंग और लैंगस्टन के लेख को समझने की कोशिश करते हैं कि मैं एल्गोरिथ्म को उस रूप में लागू करने में विफल रहा जिसमें यह वर्णित है। खंड ४.३ में वे जिस तकनीक का उपयोग करते हैं वह काम नहीं करती है क्योंकि "यह है, यह सीधे तौर पर इस प्रकार है कि दूसरी-सबलिस्ट श्रृंखला के सबसे दाहिने ब्लॉक का सिर अस्थायी रूप से रिकॉर्ड की तुलना में इसकी तात्कालिक रूप से अधिक महत्वपूर्ण रूप से महत्वपूर्ण होगा।" सही ” हमेशा सच नहीं होता है। सौभाग्य से, कुछ बाद के कार्यों में मैं इस मुसीबत के आसपास जाने का एक रास्ता खोजने में कामयाब रहा, और अब मैं कह सकता हूं कि एक एल्गोरिथ्म जो सभी तीन स्थितियों को संतुष्ट करता है वास्तव में मौजूद है।

तो चलिए शुरू करते हैं ...

मूल संचालन

सरणी के साथ काम करने के लिए, हमें कार्यों की आवश्यकता है:

• SWAP1 (ए, बी) - दो तत्वों को स्वैप करें। कठिनाई 1 है।
• SWAPN (A, B, K) - सरणियों A और B के तत्वों के स्वैप K जोड़े। जटिलता K है।
• ROTATE (A, K, L) - सरणी A के दो लगातार टुकड़ों को फिर से व्यवस्थित करें, पहले की लंबाई K है, दूसरे की लंबाई L है। जटिलता K + L से अधिक नहीं है।
• BinSearchLeft (X, A, L) - एक एलिमेंट एक्स में एक एलिमेंट एक्सरे को डालने के लिए सबसे बाईं ओर का स्थान ज्ञात करें। L की वैधता के परिणाम 0 से L तक हैं। कठिनाई लॉग (L) है।
• BinSearchRight (X, A, L) - किसी तत्व X को लंबाई L के क्रम में दिए गए ए में सम्मिलित करने के लिए सबसे सही जगह है। परिणाम के लिए मान्य मान 0 से L तक हैं। कठिनाई लॉग (L) है।

हम विनिमय के लिए एक क्लिपबोर्ड की तलाश कर रहे हैं।

पहले थोड़ी शब्दावली।
उन तत्वों के बारे में जिनके लिए तुलनात्मक फ़ंक्शन ने परिणाम दिया कि वे समान हैं, हम कहते हैं कि "उनके पास एक ही कुंजी है", हालांकि शारीरिक रूप से कोई कुंजी मौजूद नहीं हो सकती है। तदनुसार, आप सरणी में अलग-अलग कुंजी की संख्या और तत्वों को अलग-अलग कुंजी के साथ निर्धारित कर सकते हैं।

सरणी के दो राज्यों को समतुल्य कहा जाएगा यदि उनमें समान कुंजियों वाले तत्व समान क्रम में हों। स्थिर इन-प्लेस सॉर्टिंग की मुख्य समस्या यह समानता खोना नहीं है, या हमेशा इसे बहाल करने में सक्षम होना है।

सरणी की लंबाई N। यदि N <16 है, तो हम इस तरह की सरणी को सॉर्ट नहीं करेंगे, बल्कि आवेषण के साथ कॉलिंग सॉर्ट करें - यह सामान्य स्पर्शोन्मुख व्यवहार को प्रभावित नहीं करेगा।

Sqrt (N) के करीब दो की शक्ति के बराबर संख्या S चुनें। हम K = [N / S] परिभाषित करते हैं। और K + S सरणी में जोड़ीदार विभिन्न कुंजियों को खोजने का प्रयास करें।

पहला विचार यह है कि अगर हम प्रत्येक कुंजी के लिए इस कुंजी के साथ सरणी के सबसे बाएं तत्व को लेते हैं, और सरणी की शुरुआत में ऐसे सभी तत्वों को इकट्ठा करते हैं (शेष तत्वों के क्रम को संरक्षित करते हुए), तो समतुल्यता टूट नहीं जाएगी, लेकिन यह हमें एक जगह देगा जिसमें हम हम स्वतंत्र रूप से एक दूसरे के साथ तत्वों की पुन: व्यवस्था और तुलना कर सकते हैं।

खोज प्रक्रिया में, हम सरणी के निरंतर टुकड़े में पाई गई कुंजियों को रखेंगे, और इसे आगे बढ़ाएंगे क्योंकि नई कुंजियाँ मिलती हैं: सरणी के तत्वों के माध्यम से छंटनी, हम उन्हें द्विआधारी खोज के साथ मिली कुंजियों के टुकड़े में खोजेंगे, और यदि हम इसे नहीं ढूंढते हैं, तो सरणी को एक में रोटेट के साथ फिट करें। पाया तत्व की चाबियाँ, और दूसरे के लिए - इस टुकड़े में नए तत्व को सही जगह पर रखें।

कुंजी को आरोही क्रम में एकत्र किया जाता है, जो जाँच का समय बचाता है अगर हमने पहले से ही मौजूदा तत्व के समान कुंजी के साथ एक तत्व का सामना किया है। कुंजियों के साथ खंड के चाल की संख्या पाए जाने वाली कुंजियों की संख्या से अधिक नहीं है, इसलिए इस चरण की जटिलता, सबसे खराब स्थिति में, एन * लॉग (एनकेई) तुलना और 2 * एन + एनकेई के ² चरणों की है। NKeys के बाद से हमारे पास लगभग 2 * sqrt (N) हैं, अब तक हम विदेश नहीं गए हैं।

अब हमारे पास दो विकल्प हैं। या तो हमें ऑर्डर किए गए K + S कीज़ मिलीं, या हमें नहीं मिलीं। इन मामलों को थोड़ा अलग तरीके से संभाला जाता है। इसके अलावा, एक ऐसा मामला है जहां विभिन्न कुंजियों की संख्या 4 से कम है - इसके लिए भी, इसकी अपनी प्रसंस्करण है।

केस ए। कई अलग-अलग चाबियाँ हैं।

हमारे पास सरणी की शुरुआत में एकत्र की गई विभिन्न कुंजियों के K + S हैं। हम उनमें से पहले K को "टुकड़ों को चिह्नित करने के लिए कुंजी" घोषित करेंगे और अब हम स्पर्श नहीं करेंगे। शेष S मर्ज बफर होगा। मूल सरणी के सभी शेष तत्व "डेटा" हैं, अब वे सरणी के अंत में हैं।

A.1। क्लासिक मर्ज सॉर्ट चरण।

हम दो और कार्य लिखेंगे। एक को MergeLeft, दूसरे को MergeRight कहा जाएगा। वे तीन भागों से मिलकर सरणियों के टुकड़े खिलाए जाते हैं। MergeLeft के मामले में, यह लंबाई P का एक बफर है, लंबाई Q का एक सॉर्ट किया गया टुकड़ा, और लंबाई R का एक सॉर्ट किया गया टुकड़ा, जहां S≥R है। फ़ंक्शन को दूसरे और तीसरे टुकड़े को मर्ज करना चाहिए, परिणाम को शुरुआत में डाल देना चाहिए, और इस टुकड़े के अंत में यादृच्छिक क्रम में बफर तत्व। MergeRight फ़ंक्शन एक मिरर तरीके से काम करता है - इनपुट पर इसके दो सॉर्ट किए गए टुकड़े होते हैं, इसके बाद एक बफर होता है, और आउटपुट पर, इसके विपरीत, एक बफर, एक सॉर्ट किए गए टुकड़े के बाद। यह कुछ इस तरह दिखता है:

दोनों कार्यों की जटिलता Q + R से अधिक नहीं है - दोनों तुलनाओं में और आदान-प्रदान में।
MergeLeft फ़ंक्शन का उपयोग करके, हम पहले जोड़े के द्वारा डेटा को सॉर्ट कर सकते हैं, फिर चौकों द्वारा ... लंबाई के टुकड़े तक एस (मुझे याद है कि एस दो की शक्ति है)। हर बार जब एम तत्वों को छांटते हैं, तो हम लंबाई एम / 2 के बफर के एक टुकड़े का उपयोग करते हैं, जिसके परिणामस्वरूप सरणी के दाईं ओर निकल जाता है। सॉर्टिंग जोड़े के चरण में, हम लंबाई 2 के बफर के एक टुकड़े का उपयोग करेंगे, ताकि जब तक सॉर्ट किए गए टुकड़े लंबाई एस के होते हैं, तब तक डेटा सरणी बाईं ओर दबाया जाएगा, और बफर तत्वों के एस दाईं ओर होगा। अब हम मर्जाइट का उपयोग कर सकते हैं, 2 * एस लंबाई के टुकड़ों को छांट सकते हैं, और एक ही समय में, बफर को शुरुआत में वापस कर सकते हैं।

.2। ब्लॉक सॉर्टिंग चरण।

अब हमने लंबाई G = 2 * S के टुकड़े छांटे हैं। हम उन्हें जोड़े में, फिर जोड़े में, आदि में विलय कर देंगे, जब तक कि हम पूरे डेटा सरणी के आकार तक नहीं पहुंच जाते। ऐसा करने के लिए, हमारे पास लंबाई S की एक बफर और लंबाई K की कुंजियों के साथ एक सरणी है, जहां K / L / S (L डेटा सरणी की कुल लंबाई है)।
तो, चक्र "जबकि जी" एल "।

हम लंबाई जी के दो लगातार अंशों को मर्ज करना चाहते हैं, और उनके तुरंत पहले लंबाई एस (जी और एस दो की शक्तियां हैं) का एक बफर है। हमारे टुकड़ों को लंबाई के खंडों में विभाजित करें। S उन्हें बाहर आने दें K _१ । सरणी के बहुत अंत में दूसरा टुकड़ा जी की तुलना में कम लंबाई हो सकता है, और विभाजन के बाद, एक अपूर्ण ब्लॉक इससे रह सकता है, हम इसकी गणना भी करेंगे (हालांकि हम इसे स्थानांतरित नहीं करेंगे)। पहले K ₁ कुंजी लें (वे मूल सरणी की शुरुआत में हैं), उन्हें क्रमबद्ध करें (उदाहरण के लिए, आवेषण द्वारा) और संख्या G / S के साथ कुंजी का सूचकांक याद रखें (अब यह G / S है, लेकिन फिर यह बदल जाएगा) - आइए इसे midkey कहते हैं। प्रत्येक कुंजी का अपना ब्लॉक होता है। हम उनका उपयोग करते हैं, पहले, पहले और दूसरे मर्ज किए गए अंशों को भेद करने के लिए, और दूसरे, समान तत्वों वाले ब्लॉकों के क्रम को बनाए रखने के लिए। क्योंकि अब हम उन्हें भयानक रूप में मिला देंगे।

ब्लॉक को क्रमबद्ध करें। आदेश पहले तत्वों द्वारा निर्धारित किया जाएगा, और यदि वे समान हैं, तो इन ब्लॉकों के अनुरूप चाबियाँ। एकमात्र प्रकार जो हम यहां उपयोग कर सकते हैं वह न्यूनतम तत्व का चयन करके छंटनी है, क्योंकि इसके लिए K ₁ एक्सचेंज (और K ₁ 2/2 तुलना) से अधिक की आवश्यकता नहीं है: दो ब्लॉकों का आदान-प्रदान एक महंगी प्रक्रिया है, लेकिन चूंकि S sqrt (N) के बारे में है। , फिर पूरा छँटाई चरण ओ (एन) संचालन में फिट बैठता है। जब हम दो ब्लॉकों को पुनर्व्यवस्थित करते हैं, तो हम उनके अनुरूप कुंजियों को फिर से व्यवस्थित करते हैं, मिडकी कुंजी का पालन करना नहीं भूलते हैं। इस छँटाई में अपूर्ण ब्लॉक (यदि कोई हो) हम स्पर्श नहीं करते हैं!

पहले खंड से संबंधित ब्लॉक को अक्षर A द्वारा निरूपित किया जाएगा, और दूसरे से संबंधित ब्लॉक को अक्षर B से निरूपित किया जाएगा। हमारी छँटाई में, प्रत्येक टुकड़े के अनुरूप ब्लॉक का क्रम,
संरक्षित।

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

अब ब्लॉकों को मर्ज करना शुरू करते हैं। हर पल की स्थिति इस तरह होगी:

• पहले पूर्ण विलय वाले ब्लॉकों की एक निश्चित संख्या आती है, जिसके बारे में यह ज्ञात है कि अब हम उन्हें स्पर्श नहीं करते हैं।
• फिर अगले ब्लॉक के कुछ (टी, संभवतः टी = 0) तत्व, जो पहले से ही जगह में हैं।
• फिर एस बफर तत्व
• तब एसटी तत्व जिनके लिए कोई स्थान अभी तक निर्धारित नहीं किया गया है। वे सभी एक टुकड़े से संबंधित हैं - ए या बी, और हम जानते हैं कि कौन सा है।
• आगे कच्चे ब्लॉक आते हैं, जिनमें से प्रकार हम मिडक के साथ संबंधित कुंजी की तुलना करके निर्धारित कर सकते हैं।

यह कुछ इस तरह दिखता है:

यहां ए // बी सॉर्ट किया गया खंड है, ए 1 अधूरा ब्लॉक है, ए 2, ए 3, बी 2 अनप्रोसेस्ड ब्लॉक हैं, बी 3 अंत में अधूरा ब्लॉक है (यह ए 2 या ए 3 से पहले इसका वास्तविक स्थान हो सकता है)।
शुरुआत में, हमारे पास कोई मर्ज किए गए ब्लॉक नहीं हैं, टी = 0, और बफर के बाद आने वाले एसटी तत्वों का प्रकार पहली कुंजी द्वारा निर्धारित किया गया है।

अगले ब्लॉक को संसाधित करने के लिए, हमें एक और SmartMergeLeft फ़ंक्शन लिखना होगा (और यह अंतिम नहीं है!)। मर्जलेफ्ट की तरह, यह इनपुट पर एक बफर और दो टुकड़े प्राप्त करता है, और इन अंशों का क्रम गलत हो सकता है (तब विलय करते समय, समान तत्वों के मामले में दूसरे टुकड़े से एक तत्व लेना आवश्यक होगा)। फ़ंक्शन को तत्वों को केवल तब तक पुनर्व्यवस्थित करना चाहिए जब तक कि दोनों टुकड़े गैर-रिक्त न हों। जैसे ही उनमें से एक समाप्त होता है, उसे अन्य टुकड़े के शेष तत्वों को अंत तक स्थानांतरित करना चाहिए (यदि दूसरा टुकड़ा पहले समाप्त हो गया था), उनकी संख्या की रिपोर्ट करें, और वे किस टुकड़े में थे।
कुछ इस तरह:

पहले मामले में, बी से तत्व पहले समाप्त हो गए, और अंत में ए से अंतिम तत्व बने रहे, और दूसरे में, इसके विपरीत।
इस फ़ंक्शन का उपयोग करके, हम आसानी से एक ब्लॉक को आगे बढ़ा सकते हैं। यदि अगले ब्लॉक का प्रकार पिछले असंसाधित तत्वों के समान है, तो हम उन्हें बफर के साथ बदलते हैं और कहते हैं कि टी = 0, और नया ब्लॉक अनप्रोसेस्ड है (स्थिति शुरुआत में जैसी है)। यदि प्रकार अलग-अलग हैं, तो हम स्मार्टमर्लीटेफ़्ट कहते हैं, और वह सब कुछ स्वयं करती है - ऐसे तत्व जो ब्लॉक के अंत में रहते हैं और अनप्रोसेस्ड होंगे।

तो, ब्लॉकों के माध्यम से छंटनी, हम या तो अंत तक पहुंचेंगे या उस स्थान पर जहां खंड बी के अंत से अधूरा ब्लॉक खड़ा होना चाहिए। यहां हमारे पास कई विकल्प हैं।

या अंतिम शेष कच्चे तत्व खंड बी से हैं। फिर इनमें से अंतिम तत्व ब्लॉक ए से पहले तत्व से छोटा है (यदि कोई हो), और हम बफर के साथ कच्चे तत्वों का सुरक्षित रूप से आदान-प्रदान कर सकते हैं।

या ये तत्व खंड ए से हैं। फिर हम उन्हें उनके बाद (फिर से, यदि कोई हो) ब्लॉक करने के लिए लगभग पेस्ट करते हैं।
दोनों मामलों में, हमें एक ही स्थिति मिलती है - बफर, टुकड़ा ए से तत्वों के बाद, फिर टुकड़े बी से एस तत्वों से अधिक नहीं। मर्जलेफ्ट फ़ंक्शन के लिए तैयार स्थिति। हम इसे कहते हैं - और टुकड़े विलय कर रहे हैं, और बफर उनके बाद है।

जब तक हम डेटा सरणी के अंत तक नहीं पहुंच जाते, तब तक हम लंबाई G के सभी जोड़े के लिए इस प्रक्रिया से गुजरते हैं। फिर हम सभी डेटा को एस तत्वों द्वारा दाईं ओर स्थानांतरित करते हैं (बफर को शुरुआत में लौटाते हैं), और एस के मूल्य को दोगुना करते हैं।
चक्र का अंत।

A.3। समापन।

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

MergeWithoutBuffer फ़ंक्शन इनपुट के रूप में लंबाई P और Q के दो सॉर्ट किए गए टुकड़े प्राप्त करता है। मान लीजिए P <Q। जबकि पहले टुकड़े का पहला तत्व दूसरे टुकड़े के पहले तत्व से बड़ा नहीं है, हम टुकड़े को दाईं ओर शिफ्ट करते हुए पी को 1 से कम कर देंगे। यदि पी शून्य पर पहुंच जाता है, तो हम जीत गए। अन्यथा, BinSearchLeft का उपयोग करते हुए, हम दूसरे टुकड़े में पहले तत्व k की सही स्थिति k पाएंगे, और ROTATE के उपयोग से हम पहले टुकड़े और दूसरे टुकड़े के पहले k तत्वों को बदल देंगे। Q से k घटाएं, अंशों की शुरुआत करें। यदि क्यू शून्य तक पहुंचता है - फ़ंक्शन निष्पादित होता है, अन्यथा हम इसे शुरू से दोहराते हैं। इस समारोह की जटिलता P ^ 2 + Q है। यदि स्रोत P theQ था, तो हम ऐसा ही करते हैं, लेकिन एक दर्पण क्रम में।

सॉर्ट को पूरा करने के लिए, MergeWithoutBuffer (Arr, K + S, NKS) को कॉल करें। सब कुछ तैयार है।

केस बी। कुछ अलग चाबियाँ हैं, लेकिन तीन से अधिक।

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

B.1। क्लासिक मर्ज सॉर्ट चरण।

यह चरण A.1 से अलग नहीं है, केवल लंबाई S के बफ़र के बजाय हम K की लंबाई की एक सरणी का उपयोग करेंगे (यह दो की शक्ति है)। आगे और पीछे के सरणी के साथ चलते हुए, हमें लंबाई G = 2 * K के सॉर्ट किए गए टुकड़े मिलते हैं।

B.2। ब्लॉक सॉर्टिंग चरण।

मान लीजिए कि लंबाई जी के टुकड़े पहले से ही विलय हो गए हैं, और हम उन्हें जोड़े में जोड़ना चाहते हैं। चूंकि हमारे पास बफर नहीं है, इसलिए हम खुद ब्लॉक आकार का चयन कर सकते हैं। ब्लॉक को चिह्नित करने के लिए कुंजियों की संख्या K के ₁ = मिनट (K, K ₂ ) से अधिक नहीं होती है, जहां K ₂ दो के निकटतम (2 * G * M) ^1/3 की शक्ति है (याद रखें कि M विभिन्न की संख्या है सरणी में कुंजी)। ब्लॉक का आकार S = 2 * G / K _{1 होगा} ।

हम कुंजियों और ब्लॉकों को A.2 की तरह ही क्रमबद्ध करते हैं। इसके लिए किसी बफर की जरूरत नहीं है।
अब हमें सरणी के माध्यम से जाने और ब्लॉक को मर्ज करने की आवश्यकता है। चलो फ़ंक्शन लिखें स्मार्टमार्टविथआउटबफ़र, जो मर्जविथआउटबफ़र और स्मार्टमर्गेलेफ़्ट का एक संकर है। यह मानता है कि पहला टुकड़ा दूसरे से छोटा है। यह MergeWithoutBuffer के समान काम करता है, लेकिन यह ध्यान में रखता है कि टुकड़ों का क्रम गलत हो सकता है, और इसके अलावा, कितने तत्वों और किस खंड से सरणी के अंत में बने रहे, रिपोर्ट करता है। SmartMergeLeft के बजाय इस फ़ंक्शन को कॉल करना, और अंत में MergeLeft के बजाय MergeWithoutBuffer फ़ंक्शन को मर्ज किए गए टुकड़े मिलते हैं।

ऐसा लगता है कि यहां हम हार गए - सबसे खराब स्थिति में ब्लॉक की अधिकतम लंबाई (K = 4, G = N / 2) N / 4 है, जिसका अर्थ है कि SmartMergeWithoutBuffer फ़ंक्शन को O (N ^ 2) संचालन की आवश्यकता हो सकती है। लेकिन यह हमें बचाता है कि सरणी में विभिन्न कुंजियों की संख्या छोटी है - और हम दिखा सकते हैं कि SmartMergeWithoutBuffer की जटिलता P * m + Q से अधिक नहीं है, जहाँ m पहले टुकड़े में विभिन्न कुंजियों की संख्या है। और जब से लंबाई के एक टुकड़े के सभी K / 2 ब्लॉकों के लिए अलग-अलग कुंजी की संख्या का योग (एक गहरी सांस लें और फिर से पढ़ें - मैं इसे आसान नहीं बना सकता हूं) K / 2 + M से अधिक नहीं होता है, तो लंबाई के दो टुकड़े विलय करने पर G (O) से अधिक नहीं लगेगा संचालन।

B.3। समापन।

यह चरण A.3 से अलग नहीं है।

केस सी। तीन से अधिक अलग-अलग कुंजियाँ नहीं हैं।

यहां हम सामान्य मर्ज सॉर्ट लिखते हैं (पुनरावर्तन के बिना - हम 2 से सॉर्ट करते हैं, फिर 4 तत्वों द्वारा, आदि), और टुकड़ों को मर्ज करने के लिए हम मर्जविथआउटबफर्स ​​का उपयोग करते हैं। चूंकि सरणी में कुछ अलग-अलग कुंजी हैं, इसलिए इसकी जटिलता विलय की जा रही लंबाई से रैखिक होगी, जिसका अर्थ है कि समग्र जटिलता हे (एन * लॉग (एन)) है।

कार्यान्वयन और निष्कर्ष।

कार्यान्वयन बोझिल हो गया - सी ++ में लगभग 400 लाइनें (वास्तव में, यह सी में लिखा गया है - आपको कार्यों की शुरुआत में चर विवरण को स्थानांतरित करने की आवश्यकता है)। ए और बी के मामलों में ऑपरेशन की गति बहुत भिन्न होती है। सबसे खराब स्थिति तब होती है जब बहुत सारी अलग-अलग चाबियां होती हैं, लेकिन आपको केस ए में जाने की आवश्यकता से थोड़ा कम है - इस स्थिति में, एल्गोरिथ्म ए की तुलना में धीमी गति से चलता है, लगभग 3 बार। हालांकि, जटिलता अनुमान एन * लॉग (एन) संरक्षित है।

बड़े सरणियों पर (लगभग 10 मिलियन से), एल्गोरिथ्म लगभग हमेशा (अलग-अलग कुंजी की बहुत कम संख्या के मामलों को छोड़कर) आउटपरफॉर्मस इनप्लास्टेबलबोर्ट (एक जो ओ (एन * लॉग (एन) ² ) के पीछे है))। लेकिन वह std :: static_sort के साथ प्रतिस्पर्धा करने में सक्षम नहीं है: कम से कम हमेशा कुछ स्मृति होती है, और इस मामले में std :: stabil_sort जल्दी से नियमित रूप से मर्जर्ट पर स्विच करता है, और आसानी से और बिना शर्त सभी को ओवरटेक करता है, जिसमें quicksort :) भी शामिल है। तो कार्यान्वित एल्गोरिथ्म का केवल सैद्धांतिक महत्व है।

लेकिन फिर भी, यह मौजूद है :)

पुनश्च पहली तस्वीर आर। सेडग्विक, एल्गोरिथम और डेटा स्ट्रक्चर्स , प्रिंसटन यूनिवर्सिटी, स्प्रिंग 2010 के एक व्याख्यान पाठ्यक्रम की एक स्लाइड है।


अद्यतन: चरण बी 2 को बहुत तेज किया जा सकता है। जबकि संख्या जी पर्याप्त रूप से छोटी है, ऐसा हो सकता है कि (के / 2) ^ 2> = 2 * जी। इस मामले में, हम कुंजी के सेट को आधा में विभाजित कर सकते हैं, और आधे को क्लिपबोर्ड (और चाबियों के रूप में दूसरा आधा) के रूप में उपयोग कर सकते हैं, और ए 2 से तेज विधि का उपयोग करके टुकड़े को मर्ज कर सकते हैं। और जी के अंत में बफर के बिना एक्सचेंजों पर स्विच करें, जब जी सरणी के आकार के करीब पहुंचते हैं।
हमारे पास जितनी अधिक अलग-अलग कुंजियाँ होती हैं, उतने लंबे समय तक बिना बफर के काम करता है, लेकिन जितना अधिक समय तक हम इसे बिना कर सकते हैं।
प्रयोगों से पता चलता है कि सबसे खराब स्थिति में, एल्गोरिथ्म को 1.61 * N * लॉग ₂ एन एन तुलना और 2.12 * एन * लॉग ₂ एन एक्सचेंज (N≤1000000 के लिए, अलग-अलग कुंजी की पूर्व निर्धारित संख्या के साथ यादृच्छिक डेटा पर) की आवश्यकता नहीं है।