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

आज हम फिर से बेवकूफी को आधार के रूप में लेंगे और उसमें एक और छोटा लेकिन महत्वपूर्ण बदलाव करेंगे। नतीजतन, हम छंटाई एल्गोरिदम की एक पूरी तरह से अलग विकासवादी श्रृंखला प्राप्त करते हैं।

छवि: विकास

सिली तरह

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

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



खैर, उन लोगों को बधाई जो इस पद्धति के बारे में नहीं जानते थे। आप बस एक विधि से मिले जिसका नाम है ...

बौना क्रमबद्ध

छवि: डच गार्डन सूक्ति

यद्यपि बौनों ने इस पद्धति को कई शताब्दियों के लिए जाना है, मानव जाति ने हाल ही में इसके बारे में सीखा है। पहले से ही 55 साल पहले, मानव जाति ने मर्जिंग छँटाई का उपयोग किया, 40 साल बीत गए जब त्वरित छँटाई ज्ञात हो गई, और 35 साल बाद पिरामिड छँटाई विकसित हुई - और अब, केवल 2000 में, यह सरल, लगभग बचकाना तकनीक, डिक ग्रुन द्वारा अध्ययन किया गया था:

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

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



इसलिए थोड़ा तेज है, हालांकि यह अस्थायी जटिलता मौलिक रूप से नहीं सुधर रही है, और यह O ( n ² ) बनी हुई है। लेकिन दूसरी ओर, यह हमें न केवल एक नई छँटाई विधि की ओर ले जाता है, बल्कि एक पूरे नए छँटाई वर्ग तक भी पहुँचाता है। और एल्गोरिदम के इस समूह का नाम " सम्मिलन स्थल" है।

सरल सम्मिलन छँटाई

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

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



एक ही अनुकूलित "सूक्ति", लेकिन केवल विनिमय के लिए, एक बफर का उपयोग किया जाता है।

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

जैसा कि आप देख सकते हैं, हालांकि आवेषण द्वारा छंटाई स्वयं धीमी है, इसका दायरा बहुत व्यापक है।

खैर, सम्मिलन प्रकार के बारे में इतने सारे पत्र लिखे जाने के बाद से, कहानी पूरी नहीं होगी, अगर एल्गोरिथ्म के बारे में कुछ प्रकार के शब्द नहीं हैं ...

शेल सॉर्ट

हैबे पर शैल को छाँटने के बारे में पहले से ही एक लेख है , इसलिए मैं बहुत संक्षिप्त होऊंगा।

परसों मैंने पहले ही लिख दिया था कि कैसे बहुत जल्दी "कंघी" को बहुत धीमे "बबल" से बनाया जा सकता है। ऐसा करने के लिए, आपको पहले पड़ोसियों की तुलना करने की आवश्यकता नहीं है, लेकिन उन तत्वों के बीच जो एक प्रभावशाली दूरी पर्याप्त है। यह प्रारंभिक चरण में छोटे मूल्यों को सरणी की शुरुआत के करीब फेंकने की अनुमति देता है, बड़े अंत के करीब। फिर अंतर को कम करना, पहले से ही सरणी में स्थानीय आदेशों को प्रेरित करना।

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



"शेल" की समय जटिलता एक जटिल समस्या है। तथ्य यह है कि अभी भी कोई सख्त सूत्र नहीं है जिसके द्वारा उपसमूहों में तत्वों के बीच अलग-अलग दूरी की इष्टतम संख्या श्रृंखला का निर्माण किया जाता है। अनुक्रम अनुभवजन्य रूप से बनाया गया है, विभिन्न इनपुट डेटा के साथ कई परीक्षणों पर आधारित है, और उपरोक्त "डेल्टास" के लिए अंतिम सर्वश्रेष्ठ शोधन 2001 में निर्धारित किया गया था:

1, 4, 10, 23, 57, 132, 301, 701।

अजीब तरह से छंटाई का आविष्कार शेल द्वारा किया गया था, अजीब तरह से पर्याप्त, डोनाल्ड शेल 1959 में। 2014 में, लेखक, 90 वर्ष का हो गया, अभी भी जीवित है और रहता है, उसने हाल ही में तीसरी बार शादी की है। इसलिए, एल्गोरिदम का आविष्कार करें, अपने दिमाग को अच्छे आकार में रखें - और आप 3 पत्नियों से बचेंगे, जो आपके लिए दीर्घकालिक रचनात्मक गतिविधि प्रदान की जाती हैं।

संदर्भ

विकिपीडिया पर छाँटे गए एल्गोरिदम
विकिपीडिया पर एल्गोरिथ्म सॉर्टिंग
बबल सॉर्ट और ऑल-ऑल-ऑल
और फिर से छँटाई के बारे में: हम सबसे अच्छा एल्गोरिथ्म चुनते हैं
रोसेटा क्रमबद्ध कार्यान्वयन