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

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

सबसे सामान्य मामले में, यह लगभग उसी तरह से होता है। तत्व कुछ मानदंड के अनुसार कक्षाओं द्वारा बिखरे हुए हैं। यदि इससे व्यूह का क्रम नहीं बनता है, तो वर्ग की विशेषताओं को परिष्कृत किया जाता है और तत्वों को फिर से परिष्कृत कक्षाओं में बिखेर दिया जाता है। और यह तब तक होता है जब तक कि सरणी ऑर्डर नहीं हो जाती।

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

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

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

यह लेख EDISON के समर्थन से लिखा गया था।
ग्राहक राय: EDISON से प्रोग्रामर के 10 प्लस
यह जानना दिलचस्प और उपयोगी है: नाश्ता प्रोग्रामर

एक एल्गोरिथ्म पर विचार करें जो अधिकांश उत्तलता उपरोक्त गुणों को प्रदर्शित करता है।

बाल्टी प्रकार :: बाल्टी प्रकार

अन्य नाम टोकरी छँटाई, ब्लॉक छँटाई, जेब छँटाई हैं।

हम बास्केट में संख्याओं को बिखेरते हैं, फिर प्रत्येक टोकरी में हम छोटे बास्केट में बिखेरते हैं, और इसी तरह, जब तक टोकरी में कुछ स्तर पर केवल एक ही तत्व नहीं होते हैं। फिर निम्नतम स्तर के ऐसे बास्केट से एक ऑर्डर किए गए राज्य में सरणी को पुनर्स्थापित करना आसान है।

आइए हम एक विशिष्ट उदाहरण के साथ समझाते हैं। मान लीजिए कि हमारे पास एक अनियंत्रित सरणी है। यह ज्ञात है कि इस सरणी में 1 से 8 तक संख्याएँ हैं।



हम इन संख्याओं को 2 समूहों में फेंकते हैं: 1 से 4 तक की संख्याएं एक समूह में गिरती हैं, दूसरे से 5 से 8 तक। फिर हम पहली टोकरी में संख्याओं को दो टोकरी में वितरित करते हैं: एक संख्या 1 और 2 में और दूसरी 3 और 4 में। हम इन टोकरियों को बास्ट बास्केट में भी वितरित करते हैं, जिसमें पहले से ही एक ही आकार के नंबर होते हैं। 5 से 8 की संख्या वाली उस बड़ी टोकरी के लिए, हम एक समान पुनरावृत्ति लागू करते हैं।

फिर, छोटे बास्केट से, जिनमें से प्रत्येक में समान संख्याएं होती हैं, हम पूर्वता के क्रम में तत्वों को मुख्य सरणी में वापस कर देते हैं।

इस रूप में परमाणु छँटाई विशेष रूप से व्यवहार में लागू नहीं है, लेकिन यह मानक रूप से प्रदर्शित करता है कि सामान्य रूप से वितरण कार्य द्वारा सभी छँटाई कैसे होती है।

थानोस सॉर्ट :: थानोस सॉर्ट

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



तत्वों के अंकगणितीय माध्य की गणना सरणी में की जाती है और फिर सभी तत्वों को 2 समूहों में वितरित किया जाता है। अंकगणित माध्य से छोटे (या बराबर) तत्व एक समूह में जाते हैं, दूसरे समूह के अंकगणितीय माध्य से बड़े होते हैं। फिर समान क्रियाओं को दोनों समूहों पर पुनरावर्ती रूप से लागू किया जाता है - और इसी तरह कड़वे अंत तक।

और पागल टाइटेनियम के बारे में क्या? यदि यह एक यादृच्छिक सरणी है, तो अंकगणित माध्य के साथ तुलना करने पर तत्व और बड़े, के पास 50/50 का मौका है कि यह दो समूहों में से एक में जाएगा।

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



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

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

हजारों सॉर्टिंग और अंकगणितीय माध्य सॉर्टिंग गिनती प्रकार से संबंधित हैं।

गिनती के सॉर्ट

मूल विचार यह है कि हम गिनते हैं कि प्रत्येक कक्षा में कितने नंबर हैं।

काउंटिंग सॉर्ट :: काउंटिंग सॉर्ट

हम गिनती करते हैं कि सरणी में एक या एक और संख्या कितनी बार होती है। इन मात्राओं को जानने के बाद, हम जल्दी से पहले से ही ऑर्डर किए गए सरणी बनाते हैं।



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

पायथन कोड:

def CountingSort(array, mn, mx): count = defaultdict(int) for i in array: count[i] += 1 result = [] for j in range(mn,mx+1): result += [j]* count[j] return result 

कबूतर क्रमबद्ध :: कबूतर प्रकार

हम सरणी से गुजरते हैं, यदि कोई नया नंबर मिलता है, तो हम इस संख्या के काउंटर (सहायक सूची की कुंजी के रूप में) को शुरू करते हैं। यदि संख्या पहली बार सामने नहीं आई है, तो इस काउंटर के लिए वेतन वृद्धि केवल ट्रिगर है।



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

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

यदि N वस्तुओं को M कंटेनरों में वितरित किया जाता है, और N> M, तो कम से कम एक कंटेनर में एक से अधिक तत्व होते हैं।

पायथन कोड:

 def PigeOnHoleSort(a): mi = min(a) size = max(a) - mi + 1 holes = [0] * size for x in a: holes[x - mi] += 1 i = 0 for count in range(size): while holes[count] > 0: holes[count] -= 1 a[i] = count + mi i += 1 

बिट सॉर्टिंग

हम उन संख्याओं को वितरित करते हैं जिनके आधार पर संख्या की एक विशेष श्रेणी में अंक होता है। यदि हम अलग-अलग अंकों के लिए कई बार ऐसा करते हैं, तो हमें अचानक एक क्रमबद्ध सरणी मिल जाती है।

कम-क्रम बिटवाइज़ छँटाई :: एलएसडी मूलांक सॉर्ट

हम निचले अंकों से बड़े लोगों की ओर बढ़ते हैं और प्रत्येक पुनरावृत्ति पर हम सरणी के तत्वों को उस अंक के आधार पर वितरित करते हैं जो अंक में है।

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

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

उच्च-क्रम बिटवाइज़ छँटाई :: MSD मूलांक सॉर्ट

सबसे पहले, हम वरिष्ठ रैंकों के बीच वितरित करते हैं, जिससे हम छोटे लोगों की ओर बढ़ते हैं।

इस विकल्प को लागू करना अधिक कठिन है, क्योंकि निचले अंकों में संक्रमण कक्षाओं के अंदर पुनरावर्ती रूप से किया जाता है, और सरणी के सभी तत्वों के बीच नहीं।

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

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

बिटवाइज़ सॉर्टिंग की गिनती

कभी-कभी वितरण छँटाई एक साथ गणना योग्य और बिटवाइज़ होती है।

मनका क्रम :: मनका क्रम

एल्गोरिथ्म के अन्य नाम: अबेकस सॉर्टिंग, ग्रेविटी सॉर्टिंग।

मैंने पहले ही एक-दो बार ( 1 , 2 ) को छांटने के बारे में लिखा था, इसलिए मुझे संक्षेप में, केवल सार होगा।

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

यहाँ चाल यह है कि हम प्रत्येक संख्या को गेंदों का उपयोग करते हुए एक संख्या प्रणाली में दर्शाते हैं। और वास्तव में, हम केवल यह गिनते हैं कि कितनी बार सभी संख्याओं में प्रत्येक अंक है।

एक पंक्ति में पायथन में बीएडसॉर्ट:

 #!/bin/python3 from itertools import zip_longest def beadsort(l): return list(map(sum, zip_longest(*[[1] * e for e in l], fillvalue=0))) 

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

संदर्भ

बाल्टी / बाल्टी , गिनती / कबूतर / डिरिचलेट , रेडिक्स / डिस्चार्ज , बीड

श्रृंखला लेख:

• एक्सेल आवेदन AlgoLab.xlsm
• एक्सचेंज सॉर्ट
• निवेशन शॉर्ट्स
• चयन के आधार पर छाँटें
• मर्ज करना
• वितरण के आधार पर छाँटें
  • अनुमानित वितरण के साथ गिनती
  • अमेरिकी ध्वज क्रमबद्ध
  • बिटवाइज़ सॉर्टिंग में प्रत्यय का पेड़
  • वितरण द्वारा छंटाई तुलना
• हाइब्रिड सॉर्टिंग

AlgoLab एक्सेल एप्लिकेशन को काफी अपडेट किया गया है। आज के लेख के कुछ एल्गोरिदम पहली बार वहां दिखाई दिए। अपडेट करें कि कौन उपयोग कर रहा है।