बकेट सॉर्ट

बकेट सॉर्ट

Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O\left(n^{2}\right)$
Average performance	$O\left(n+{\frac {n^{2}}{k}}+k\right)$, where k is the number of buckets. $O(n),{\text{when }}k\approx n$.
Worst-case space complexity	$O(n+k)$

तत्वों को डिब्बे के बीच वितरित किया जाता है

फिर, तत्वों को प्रत्येक बिन के भीतर क्रमबद्ध किया जाता है

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

बकेट सॉर्ट इस प्रकार काम करता है:

1. शुरू में खाली बाल्टियों की एक श्रृंखला स्थापित करें।
2. स्कैटर: प्रत्येक ऑब्जेक्ट को उसकी बकेट में डालते हुए, मूल सरणी पर जाएं।
3. प्रत्येक गैर-खाली बाल्टी को क्रमबद्ध करें।
4. इकट्ठा करें: बाल्टियों को क्रम से देखें और सभी तत्वों को मूल सरणी में वापस रखें।

छद्मकोड

फ़ंक्शन BucketSort(array, k) है
    बकेट ← k खाली सूचियों की नई सारणी
    एम ← 1 + सरणी में अधिकतम कुंजी मान
    i = 0 से लंबाई (सरणी) के लिए करें
        सरणी[i] को बाल्टी[तल(k × सारणी[i] / M)] में डालें
    i = 0 से k के लिए
        अगलासॉर्ट(बाल्टी[i])
    बकेट[0], ...., बकेट[k] का संयोजन लौटाएँ

मान लीजिए सारणी सॉर्ट किए जाने वाले सरणी को दर्शाती है और k उपयोग की जाने वाली बाल्टियों की संख्या को दर्शाती है। कोई भी सभी कुंजियों को एक बार दोहराकर रैखिक समय में अधिकतम कुंजी मान की गणना कर सकता है। फर्श समारोह का उपयोग फ़्लोटिंग नंबर को पूर्णांक में बदलने के लिए किया जाना चाहिए (और संभवतः डेटाटाइप की कास्टिंग भी)। फ़ंक्शन नेक्स्टसॉर्ट एक सॉर्टिंग फ़ंक्शन है जिसका उपयोग प्रत्येक बकेट को सॉर्ट करने के लिए किया जाता है। परंपरागत रूप से, [[चयन छांटना]] का उपयोग किया जाता है, लेकिन अन्य एल्गोरिदम का भी उपयोग किया जा सकता है, जैसे चयन सॉर्ट या मर्ज़ सॉर्ट । बकेटसॉर्ट को नेक्स्टसॉर्ट के रूप में उपयोग करने से रेडिक्स सॉर्ट का एक रिश्तेदार उत्पन्न होता है; विशेष रूप से, मामला एन = 2 जल्दी से सुलझाएं से मेल खाता है (हालांकि संभावित रूप से खराब धुरी विकल्पों के साथ)।

विश्लेषण

सबसे खराब स्थिति का विश्लेषण

जब इनपुट में कई कुंजियाँ होती हैं जो एक-दूसरे के करीब होती हैं (क्लस्टरिंग), तो उन तत्वों को एक ही बाल्टी में रखे जाने की संभावना होती है, जिसके परिणामस्वरूप कुछ बाल्टियों में औसत से अधिक तत्व होते हैं। सबसे खराब स्थिति तब होती है जब सभी तत्वों को एक ही बाल्टी में रखा जाता है। उदाहरण के लिए, समग्र प्रदर्शन तब प्रत्येक बकेट को सॉर्ट करने के लिए उपयोग किए जाने वाले एल्गोरिदम पर हावी होगा $O(n^{2})$ प्रविष्टि प्रकार या $O(n\log(n))$ तुलना सॉर्ट एल्गोरिदम, जैसे मर्ज सॉर्ट।

औसत-मामला विश्लेषण

इस मामले पर विचार करें कि इनपुट समान रूप से वितरित है। पहला चरण, जो बकेट को प्रारंभ करना और सरणी में अधिकतम कुंजी मान ढूंढना है, में किया जा सकता है $O(n)$ समय। यदि विभाजन और गुणा निरंतर समय में किया जा सकता है, तो प्रत्येक तत्व को उसकी बाल्टी में बिखेरने में भी लागत आती है $O(n)$. मान लें कि प्रत्येक बकेट को सॉर्ट करने के लिए इंसर्शन सॉर्ट का उपयोग किया जाता है, तो तीसरे चरण की लागत आती है $O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})$, कहाँ $n_{i}$ अनुक्रमित बाल्टी की लंबाई है $i$. चूँकि हम औसत समय, अपेक्षा से संबंधित हैं $E(n_{i}^{2})$ इसके बजाय मूल्यांकन करना होगा। होने देना $X_{ij}$ वह यादृच्छिक चर हो $1$ यदि तत्व $j$ बाल्टी में रखा जाता है $i$, और $0$ अन्यथा। अपने पास $n_{i}=\sum _{j=1}^{n}X_{ij}$. इसलिए,

${\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{l=1}^{n}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{l=1}^{n}X_{ij}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,l\leq n}\sum _{j\neq l}X_{ij}X_{il}\right)\end{aligned}}$

अंतिम पंक्ति मामले में सारांश को अलग करती है $j=l$ और मामला $j\neq l$. चूंकि किसी वस्तु को बाल्टी में वितरित करने का मौका है $i$ है $1/k$, $X_{ij}$ संभावना के साथ 1 है $1/k$ और 0 अन्यथा.

$E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}$

$E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}$

सारांश के साथ, यह होगा

$E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}$

अंततः, जटिलता होगी $O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)$.

बकेट सॉर्ट का अंतिम चरण, जो प्रत्येक बकेट में सभी सॉर्ट की गई वस्तुओं को संयोजित करना है, की आवश्यकता है $O(k)$ समय। इसलिए, कुल जटिलता है $O\left(n+{\frac {n^{2}}{k}}+k\right)$. ध्यान दें कि यदि k को चुना गया है $k=\Theta (n)$, फिर बकेट सॉर्ट चलता है $O(n)$ औसत समय, समान रूप से वितरित इनपुट दिया गया।

अनुकूलन

एक सामान्य अनुकूलन यह है कि बकेट के अवर्गीकृत तत्वों को पहले मूल सरणी में वापस रखा जाए, फिर संपूर्ण सरणी पर सम्मिलन सॉर्ट चलाया जाए; क्योंकि प्रविष्टि प्रकार का रनटाइम इस पर आधारित होता है कि प्रत्येक तत्व अपनी अंतिम स्थिति से कितनी दूर है, तुलनाओं की संख्या अपेक्षाकृत कम रहती है, और सूची को स्मृति में सन्निहित रूप से संग्रहीत करके स्मृति पदानुक्रम का बेहतर उपयोग किया जाता है। यदि इनपुट वितरण ज्ञात है या अनुमान लगाया जा सकता है, तो अक्सर ऐसी बाल्टियाँ चुनी जा सकती हैं जिनमें स्थिर घनत्व होता है (केवल स्थिर आकार के बजाय)। यह अनुमति देता है $O(n)$ समान रूप से वितरित इनपुट के बिना भी औसत समय जटिलता।

वेरिएंट

जेनेरिक बकेट सॉर्ट

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

प्रोक्समैपसॉर्ट

Main article: Proxmap sort

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

हिस्टोग्राम सॉर्ट

बकेट सॉर्ट का एक अन्य प्रकार जिसे हिस्टोग्राम सॉर्ट या गिनती क्रम के रूप में जाना जाता है, एक प्रारंभिक पास जोड़ता है जो गिनती सरणी का उपयोग करके प्रत्येक बकेट में आने वाले तत्वों की संख्या की गणना करता है। इस जानकारी का उपयोग करके, सरणी मानों को एक्सचेंजों के अनुक्रम द्वारा बाल्टी के अनुक्रम में व्यवस्थित किया जा सकता है, जिससे बाल्टी भंडारण के लिए कोई जगह नहीं बचती है।Template:Not in source

डाकिया का प्रकार

पोस्टमैन का सॉर्ट बकेट सॉर्ट का एक प्रकार है जो तत्वों की पदानुक्रमित संरचना का लाभ उठाता है, जिसे आमतौर पर विशेषताओं के एक सेट द्वारा वर्णित किया जाता है। यह डाकघरों में पत्र-छँटाई मशीनों द्वारा उपयोग किया जाने वाला एल्गोरिदम है: मेल को पहले घरेलू और अंतर्राष्ट्रीय के बीच क्रमबद्ध किया जाता है; फिर राज्य, प्रांत या क्षेत्र द्वारा; फिर गंतव्य डाकघर से; फिर मार्गों आदि द्वारा। चूँकि कुंजियों की एक-दूसरे से तुलना नहीं की जाती है, इसलिए छँटाई का समय O(cn) है, जहाँ c कुंजी के आकार और बकेट की संख्या पर निर्भर करता है। यह मूलांक प्रकार के समान है जो ऊपर से नीचे, या सबसे महत्वपूर्ण अंक पहले काम करता है।

फेरबदल प्रकार

फेरबदल प्रकार बकेट सॉर्ट का एक प्रकार है जो सॉर्ट किए जाने वाले n आइटमों के पहले 1/8 को हटाकर शुरू होता है, उन्हें पुनरावर्ती रूप से सॉर्ट करता है, और उन्हें एक सरणी में रखता है। इससे n/8 बाल्टियाँ बनती हैं जिनमें शेष 7/8 वस्तुएँ वितरित की जाती हैं। फिर प्रत्येक बाल्टी को क्रमबद्ध किया जाता है, और बाल्टी को एक क्रमबद्ध सरणी में संयोजित किया जाता है।

अन्य सॉर्टिंग एल्गोरिदम के साथ तुलना

बकेट सॉर्ट को गिनती सॉर्ट के सामान्यीकरण के रूप में देखा जा सकता है; वास्तव में, यदि प्रत्येक बाल्टी का आकार 1 है तो बाल्टी सॉर्ट गिनती सॉर्ट में बदल जाता है। बकेट सॉर्ट का परिवर्तनशील बकेट आकार इसे O(M) मेमोरी के बजाय O(n) मेमोरी का उपयोग करने की अनुमति देता है, जहां M विशिष्ट मानों की संख्या है; बदले में, यह प्रकार के O(n + M) सबसे खराब स्थिति वाले व्यवहार की गिनती करना छोड़ देता है।

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

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

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

संदर्भ

• Paul E. Black "Postman's Sort" from Dictionary of Algorithms and Data Structures at NIST.
• Robert Ramey '"The Postman's Sort" C Users Journal Aug. 1992
• NIST's Dictionary of Algorithms and Data Structures: bucket sort

बाहरी संबंध

• Bucket Sort Code for Ansi C
• Variant of Bucket Sort with Demo