🏂🏾 👨🏼‍🎤 🍺 हाइब्रिड सॉर्टिंग 🌼 👨🏻‍✈️ 🔀

जैसा कि हर कोई पहले से ही जानता है, छंटनी एक्सचेंजों, आवेषण, चयन, विलय और वितरण पर आधारित हो सकती है।

लेकिन अगर एल्गोरिथ्म में विभिन्न तरीकों को जोड़ा जाता है, तो यह हाइब्रिड प्रकारों के वर्ग के अंतर्गत आता है।

यह लेख EDISON के समर्थन से लिखा गया था।

हम 1C-Bitrix पर साइटों के पूरा होने और रखरखाव में लगे हुए हैं, साथ ही साथ मोबाइल एप्लिकेशन Android और iOS के विकास के लिए भी हैं ।

हम एल्गोरिदम के सिद्धांत से प्यार करते हैं! ;-)

आइए जल्दी से याद करें कि एल्गोरिदम की छंटाई करने वाले वर्ग क्या हैं और उनमें से प्रत्येक की विशेषताएं क्या हैं।

एक्सचेंज सॉर्ट

सरणी के तत्वों की तुलना एक दूसरे के साथ जोड़े में की जाती है और अव्यवस्थित जोड़े के लिए आदान-प्रदान किया जाता है।

इस वर्ग का सबसे प्रभावी प्रतिनिधि पौराणिक त्वरित प्रकार है ।

निवेशन शॉर्ट्स

सरणी के अनसोल्ड हिस्से से तत्वों को उनके स्थान पर सॉर्ट किए गए क्षेत्र में डाला जाता है।

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

बाइनरी सर्च ट्री का उपयोग करके छंटनी भी इसी वर्ग की है।

चयन के आधार पर छाँटें

अनियंत्रित क्षेत्र में, न्यूनतम / अधिकतम तत्व का चयन किया जाता है, जो कि सरणी के अनसरेक्टेड भाग के अंत / शुरुआत में स्थानांतरित किया जाता है।

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

मर्ज करना

सॉर्ट किए गए क्षेत्रों को सरणी में ले जाया जाता है और उन्हें विलय कर दिया जाता है, अर्थात, छोटे सॉर्ट किए गए सबरेज़ को बड़े सॉर्ट किए गए सबर्रे में संयोजित किया जाता है।

यदि दो उप-प्रकारों को क्रमबद्ध किया जाता है, तो उनका संयोजन एक आसान-से-कार्यान्वयन और तेज़-समय संचालन है। सिक्के का दूसरा पहलू यह है कि विलय में लगभग हमेशा अतिरिक्त O ( n ) मेमोरी की लागत की आवश्यकता होती है - हालाँकि विशेष रूप से परिष्कृत मर्ज सॉर्टिंग विकल्पों में से एक बहुत कम संख्या ज्ञात है, जहाँ मेमोरी कॉस्ट O (1) है।

वितरण के आधार पर छाँटें

सरणी के तत्वों को तब तक वर्गों में वितरित और पुनर्वितरित किया जाता है जब तक कि सरणी एक सॉर्ट की गई स्थिति को स्वीकार नहीं कर लेती।

तत्व समूहों में या तो उनके मूल्य (तथाकथित गिनती सॉर्टिंग ) या व्यक्तिगत अंकों के मूल्य पर निर्भर करते हुए बिखरे हुए हैं (ये पहले से ही बिटवाइज़ सॉर्टिंग हैं )।

बाल्टी छँटाई भी इसी वर्ग की है।

वितरण द्वारा छंटनी की एक विशेषता यह है कि वे या तो आपस में तत्वों की जोड़ीदार तुलना का उपयोग नहीं करते हैं, या ऐसी तुलनाएं कुछ हद तक मौजूद हैं। इसलिए, वितरण द्वारा छँटाई अक्सर गति से आगे होती है, उदाहरण के लिए, त्वरित छँटाई। दूसरी ओर, वितरण द्वारा छँटाई करने के लिए अक्सर अतिरिक्त मेमोरी की आवश्यकता होती है, क्योंकि लगातार पुनर्वितरित तत्वों के समूहों को कहीं संग्रहीत करने की आवश्यकता होती है।

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

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

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

सम्मिलित + करें

एक विशुद्ध रूप से अनुभवजन्य निष्कर्ष यह है कि संलयन और / या सम्मिलन का उपयोग अक्सर संकर में किया जाता है। अधिकांश सॉर्टिंग में, एक या दूसरी विधि पाई जाती है, या दोनों एक साथ। और इसके लिए एक तार्किक व्याख्या है।

सॉर्ट आविष्कारक अक्सर समानांतर एल्गोरिदम बनाने का प्रयास करते हैं जो एक साथ एक सरणी के विभिन्न हिस्सों को क्रमबद्ध करते हैं। कई सॉर्ट किए गए सबरेज़ से निपटने का सबसे अच्छा तरीका उन्हें मर्ज करना है - यह सबसे तेज़ होगा।

आधुनिक एल्गोरिदम अक्सर पुनरावृत्ति का उपयोग करते हैं। एक पुनरावर्ती वंश के दौरान, सरणी को आमतौर पर दो भागों में विभाजित किया जाता है, निम्नतम स्तर पर, सरणी का आदेश दिया जाता है। जब उच्च स्तर की पुनरावृत्ति पर लौटते हैं, तो सवाल निचले स्तरों पर छंटनी वाली उपमाओं के संयोजन का होता है।

आवेषण के लिए, हाइब्रिड एल्गोरिदम में कुछ चरणों में अक्सर लगभग ऑर्डर किए गए सबरेज़ प्राप्त होते हैं, जो आवेषण की मदद से अंतिम ऑर्डर करने के लिए सबसे अच्छा नेतृत्व करते हैं।

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

मर्ज-सम्मिलन प्रकार
फोर्ड जॉनसन एल्गोरिथम :: फोर्ड-जॉनसन एल्गोरिथ्म

मर्ज + डालें

एक बहुत ही प्राचीन तरीका, पहले से ही 1959 में। यह डोनाल्ड नथ के अमर काम, "प्रोग्रामिंग की कला," खंड 3, "छंटनी और खोज," अध्याय 5, "छंटनी," खंड 5.3, "इष्टतम छँटाई," उपधारा, "छँटाई की एक न्यूनतम संख्या के साथ," और आवेषण द्वारा भाग "का विस्तार से वर्णन किया गया है।" ।

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

टिम सॉर्ट :: Timsort

सम्मिलित + करें

टिम पीटर्स द्वारा 15 साल पहले और अब पोस्ट किया गया

Habré पर छंटाई को बहुत बार याद किया जाता है।
थीसिस: एक सरणी में, लगभग ऑर्डर किए गए छोटे सबरेज़ खोजे जाते हैं जिनके लिए सम्मिलन छँटाई का उपयोग किया जाता है। फिर इन उपग्रहों को मर्ज का उपयोग करके मिला दिया जाता है।

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

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

ब्लॉक मर्ज सॉर्ट :: ब्लॉक मर्ज सॉर्ट
विकी-सॉर्ट :: विकी-सॉर्ट
पवित्र कंघी बनानेवाले की रेती :: ::

आवेषण + मर्ज + बाल्टी

विकिपीडिया से ब्लॉक मर्जिंग एनीमेशन।

यह एक बहुत ताज़ा (2008) है और एक ही समय में बहुत आशाजनक एल्गोरिदम है। तथ्य यह है कि विलय की अपेक्षाकृत महत्वपूर्ण समस्या अतिरिक्त मेमोरी की लागत है। आमतौर पर, जहाँ विलय होता है, वहाँ O ( n ) मेमोरी जटिलता भी होती है।

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

कुछ वाक्यों में समझाने के लिए एल्गोरिथ्म बहुत जटिल है। लेकिन किसी दिन मैं उसके बारे में एक अलग निवास स्थान लिखूंगा।

प्रारंभ में, एल्गोरिथ्म को स्पष्ट रूप से ब्लॉक मर्ज सॉर्ट कहा जाता था, लेकिन टिम पीटर्स के हल्के हाथ के साथ, जिन्होंने छंटाई का विस्तार से अध्ययन किया (यह निर्धारित करने के लिए कि क्या इसके कुछ विचारों को टिमसर्ट में स्थानांतरित किया जाना चाहिए), विकीसोर्ट नाम इसका नाम है।

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

हैश टेबल सॉर्ट :: हैश टेबल सॉर्ट

वितरण + सम्मिलित + विलय

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

मैंने इस एल्गोरिथम के बारे में एक महीने पहले कुछ और बात की थी ।

प्राथमिक के रूप में त्वरित प्रकार

विलय और सम्मिलित करने के बाद, हाइब्रिड हिट परेड में तीसरा स्थान हर किसी के पसंदीदा त्वरित प्रकार से होता है।

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

इंट्रोस्पेक्टिव सॉर्ट :: इंट्रोस्पोर्ट, इंट्रोस्पेक्टिव सॉर्ट, एसटीडी :: सॉर्ट

तेज + ढेर + आवेषण

हीप छँटाई तेजी से छँटाई की तुलना में कुछ धीमी है, लेकिन एक ही समय में, क्विकॉर्ट के विपरीत, इसमें पतित मामले नहीं होते हैं - औसत, सबसे अच्छा और सबसे खराब एल्गोरिदमिक समय जटिलता ओ ( एन लॉग एन ) है।

इसलिए, डेविड मूसर ने त्वरित छंटाई के दौरान सुरक्षित रहने का प्रस्ताव दिया - यदि बहुत अधिक घोंसले का शिकार है, तो इसे सिस्टम पर हमला माना जाता है, जो "खराब" सरणी को फिसल गया। एक ढेर द्वारा छाँटने के लिए स्विचिंग होती है, जो मेगाबाइट नहीं है, लेकिन किसी भी आने वाले डेटा का सामना करने के लिए धीमी नहीं है।

C ++ में एक एल्गोरिथ्म है जिसे std :: सॉर्ट कहा जाता है, जो कि आत्मनिरीक्षण छँटाई का एक कार्यान्वयन है। एक छोटा सा जोड़ - यदि पुनरावृत्ति के अगले स्तर पर सबअरे के तत्वों की संख्या , 16 है , तो सबर्रे पर सम्मिलन छँटाई को लागू किया जाता है।

मल्टीके सॉर्ट :: मल्टीके सॉर्ट
बिटवाइज़ क्विक सॉर्ट :: रेडिक्स क्विक सॉर्ट

तेज + रंक

त्वरित छँटाई, केवल सरणी के तत्वों के मूल्यों की एक दूसरे के साथ तुलना की जाती है, लेकिन उनके व्यक्तिगत अंक (पहले, हम इस तरह से उच्च अंकों की व्यवस्था करते हैं, हम छोटे लोगों से उनके पास जाते हैं)।

या तो - यह उच्च क्रम से बिटवाइज़ सॉर्टिंग है, अगले बिट के अंदर ऑर्डर त्वरित सॉर्ट एल्गोरिथ्म के अनुसार किया जाता है।

स्कैटर सॉर्ट :: स्प्रेडोर्ट

फास्ट + मर्ज + बकेट + डिस्चार्ज

क्विकॉर्ट से गेस्टाल्ट, मर्ज सॉर्ट, बकेट सॉर्ट, और बिटवाइज़ सॉर्ट।

संक्षेप में नहीं समझाते। हम निम्नलिखित लेखों में से एक में इस एल्गोरिदम का विस्तार से विश्लेषण करेंगे।

अन्य संकर

वृक्ष-गिनती के प्रकार

गिनती + पेड़

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

जे-सॉर्ट :: जे-सॉर्ट

ढेर + आवेषण

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