बकेट सॉर्ट: Difference between revisions

बकेट सॉर्ट
Class	Sorting algorithm
Data structure	Array
Worst-case performance
Average performance	, where k is the number of buckets. .
Worst-case space complexity

Revision as of 01:03, 2 August 2023

एलिमेंट्स को बॉक्स के बीच डिस्ट्रीब्यूट किया जाता है

फिर, एलिमेंट्स को प्रत्येक बिन के भीतर सॉर्ट किया जाता है

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

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

इनीशिअली एम्प्टी बकेट की एक श्रृंखला सेट अप करें।
स्कैटर: प्रत्येक ऑब्जेक्ट को उसकी बकेट में डालते हुए, ओरिजिनल ऐरे पर जाएं।
प्रत्येक नॉन-एम्प्टी बकेट को सॉर्ट करें।
गैदर: बकेट को आर्डर से देखें और सभी एलिमेंट्स को ओरिजिनल ऐरे में वापस रखें।

स्यूडोकोड

function bucketSort(array, k) is
    buckets ← new array of k empty lists
    M ← 1 + the maximum key value in the array
    for i = 0 to length(array) do
        insert array[i] into buckets[floor(k × array[i] / M)]
    for i = 0 to k do 
        nextSort(buckets[i])
    return the concatenation of buckets[0], ...., buckets[k]

मान लीजिए ऐरे सॉर्ट किए जाने वाले ऐरे को दर्शाती है और k उपयोग किये जाने वाले बकेट नंबर को दर्शाती है। कोई भी सभी कीस को एक बार दोहराकर लीनियर टाइम में अधिकतम की वैल्यू की गणना कर सकता है। फ्लोर फंक्शन का उपयोग फ़्लोटिंग नंबर को इन्टिजर में बदलने के लिए किया जाना चाहिए (और संभवतः डेटाटाइप की कास्टिंग भी)। फ़ंक्शन नेक्स्टसॉर्ट एक सॉर्टिंग फ़ंक्शन है जिसका उपयोग प्रत्येक बकेट को सॉर्ट करने के लिए किया जाता है। कन्वेंशनली, इंसर्शन सॉर्ट का उपयोग किया जाता है, लेकिन अन्य एल्गोरिदम का भी उपयोग किया जा सकता है, जैसे सिलेक्शन सॉर्ट या मर्ज़ सॉर्ट। बकेटसॉर्ट को नेक्स्टसॉर्ट के रूप में उपयोग करने से रेडिक्स सॉर्ट का एक रिलेटिव उत्पन्न होता है; स्पेशल रूप से, केस n = 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)$ एवरेज टाइम पर चलता है, जहाँ समान रूप से डिस्ट्रीब्यूट इनपुट दिया गया। ^[1]

ऑप्टिमाइजेशन

एक सामान्य ऑप्टिमाइजेशन यह है कि बकेट के अनसोर्टेड एलिमेंट्स को पहले ओरिजिनल ऐरे में वापस रखा जाए, फिर संपूर्ण ऐरे पर इंसर्शन सॉर्ट चलाया जाए; क्योंकि इंसर्शन सॉर्ट का रनटाइम इस पर आधारित होता है कि प्रत्येक एलिमेंट अपनी फाइनल पोजीशन से कितनी दूर है, कमपैरीजन नंबर रेलटीवेली कम रहती है, और सूची को मेमोरी में कंटिगोस्ली स्टोर करके मेमोरी हायरार्की का बेहतर उपयोग किया जाता है। ^[2]

यदि इनपुट डिस्ट्रीब्यूटिंग ज्ञात है या एस्टीमेट किया जा सकता है, तो प्रायः ऐसी बकेट चुनी जा सकती हैं जिनमें कांस्टेंट डेंसिटी होता है (केवल कांस्टेंट साइज के स्थान पर)। यह समान रूप से वितरित इनपुट के बिना भी $O(n)$ एवरेज टाइम कॉम्पलेक्सिटी की अनुमति देता है।

वेरिएंट

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

बकेट सॉर्ट का सबसे सामान्य वैरिएंट शून्य और कुछ मैक्सिमम वैल्यू m के बीच n न्यूमेरिक इनपुट की एक सूची पर काम करता है और वैल्यू रेंज को प्रत्येक साइज m/n के n बकेट में डिवाइड करता है। यदि प्रत्येक बकेट को इंसर्शन सॉर्ट का उपयोग करके सॉर्ट किया जाता है, तो सॉर्ट को एक्सपेक्टेड लीनियर टाइम में चलते हुए दिखाया जा सकता है (जहां सभी पॉसिबल इनपुट पर औसत लिया जाता है)। ^[3] हालाँकि, इस प्रकार का परफॉरमेंस क्लस्टरिंग के साथ डीग्रेड हो जाता है; यदि कई वैल्यू एक साथ आती हैं, तो वे सभी एक ही बकेट में गिर जाएंगे और धीरे-धीरे सॉर्ट हो जाएंगे। यह मानते हुए कि इनपुट एक रैंडम प्रोसेस द्वारा उत्पन्न होता है जो इंटरवल [0,1) पर एलिमेंट्स को यूनिफोर्मली डिस्ट्रीब्यूट करता है, इस परफॉरमेंस डिग्रडेशन को ओरिजिनल बकेट सॉर्ट एल्गोरिदम में टाला जाता है। ^[1]

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

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

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

बकेट सॉर्ट का एक अन्य प्रकार जिसे हिस्टोग्राम सॉर्ट या काउंटिंग सॉर्ट के रूप में जाना जाता है, एक इनिशियल पास जोड़ता है जो काउंटिंग ऐरे का उपयोग करके प्रत्येक बकेट में आने वाले एलिमेंट्स की नंबर की गणना करता है। ^[4] इस इनफार्मेशन का उपयोग करके, ऐरे वैल्यू को एक्सचेंजों के सीक्वेंस द्वारा बकेट के सीक्वेंस में अररेंज किया जा सकता है, जिससे बकेट स्टोरेज के लिए कोई स्पेस नहीं बचती है।

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

पोस्टमैन सॉर्ट बकेट सॉर्ट का एक प्रकार है जो एलिमेंट्स की हायरार्चिकाल स्ट्रक्चर का लाभ उठाता है, जिसे सामान्यतः एट्रिब्यूट के एक सेट द्वारा वर्णित किया जाता है। यह डाकघरों में लेटर-सॉर्टिंग मशीनों द्वारा उपयोग किया जाने वाला एल्गोरिदम है: मेल को पहले डोमेस्टिक और इंटरनेशनल के बीच सॉर्ट किया जाता है; फिर स्टेट, प्रोविंस या टेरिटरी द्वारा; फिर डेस्टिनेशन पोस्टऑफिस से; फिर रुट्स आदि द्वारा। चूँकि कीस की एक-दूसरे से कम्पेरिज़न नहीं की जाती है, इसलिए सॉर्टिंग टाइम O(cn) है, जहाँ c की के साइज और बकेट के नंबर पर निर्भर करता है। यह मूलांक प्रकार के समान है जो ऊपर से नीचे, या मोस्ट सिग्नीफिकेंट डिजिट पहले काम करता है। ^[5]

शफल सॉर्ट

शफल सॉर्ट ^[6] बकेट सॉर्ट का एक प्रकार है जो सॉर्ट किए जाने वाले n आइटमों के पहले 1/8 को हटाकर प्रारम्भ होता है, उन्हें पुनरावर्ती रूप से सॉर्ट करता है, और उन्हें एक ऐरे में रखता है। इससे n/8 बकेट बनती हैं जिनमें शेष 7/8 आइटम डिस्ट्रीब्यूट की जाती हैं। फिर प्रत्येक बकेट को सॉर्ट किया जाता है, और बकेट को एक सॉर्ट ऐरे में कोंसटेनटिंग किया जाता है।

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

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

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

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

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

संदर्भ

↑ ^1.0 ^1.1 Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest & Clifford Stein. Introduction to Algorithms. Bucket sort runs in linear time on the average. Like counting sort, bucket sort is fast because it assumes something about the input. Whereas counting sort assumes that the input consists of integers in a small range, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval [0,1). The idea of bucket sort is to divide the interval [0, 1) into n equal-sized subintervals, or buckets, and then distribute the n input numbers into the buckets. Since the inputs are uniformly distributed over [0, 1), we don't expect many numbers to fall into each bucket. To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing the elements in each.
↑ Corwin, E. and Logar, A. "Sorting in linear time — variations on the bucket sort". Journal of Computing Sciences in Colleges, 20, 1, pp.197–202. October 2004.
↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.4: Bucket sort, pp.174–177.
↑ NIST's Dictionary of Algorithms and Data Structures: histogram sort
↑ "Robert Ramey Software Development".
↑ A revolutionary new sort from John Cohen Nov 26, 1997

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

बाहरी संबंध

[lfcs-1] 1.0 ^1.1 Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest & Clifford Stein. Introduction to Algorithms. Bucket sort runs in linear time on the average. Like counting sort, bucket sort is fast because it assumes something about the input. Whereas counting sort assumes that the input consists of integers in a small range, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval [0,1). The idea of bucket sort is to divide the interval [0, 1) into n equal-sized subintervals, or buckets, and then distribute the n input numbers into the buckets. Since the inputs are uniformly distributed over [0, 1), we don't expect many numbers to fall into each bucket. To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing the elements in each.

[2] Corwin, E. and Logar, A. "Sorting in linear time — variations on the bucket sort". Journal of Computing Sciences in Colleges, 20, 1, pp.197–202. October 2004.

[3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.4: Bucket sort, pp.174–177.

[4] NIST's Dictionary of Algorithms and Data Structures: histogram sort

[5] "Robert Ramey Software Development".

[6] A revolutionary new sort from John Cohen Nov 26, 1997

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 8: / Line 8: @@
 }}
-[[File:Bucket sort 1.svg|right|frame|तत्वों को डिब्बे के बीच वितरित किया जाता है]]
+[[File:Bucket sort 1.svg|right|frame|एलिमेंट्स को बॉक्स के बीच डिस्ट्रीब्यूट किया जाता है]]
-[[File:Bucket sort 2.svg|right|frame|फिर, तत्वों को प्रत्येक बिन के भीतर क्रमबद्ध किया जाता है]]बकेट सॉर्ट, या बिन सॉर्ट, एक [[छँटाई एल्गोरिथ्म]] है जो ऐरे डेटा संरचना के तत्वों को कई बकेट में वितरित करके काम करता है। फिर प्रत्येक बकेट को अलग-अलग सॉर्ट किया जाता है, या तो एक अलग सॉर्टिंग एल्गोरिदम का उपयोग करके, या बकेट सॉर्टिंग एल्गोरिदम को पुनरावर्ती रूप से लागू करके। यह एक वितरण सॉर्ट है, [[कबूतरखाना प्रकार]] का एक सामान्यीकरण जो प्रति बाल्टी कई कुंजियों की अनुमति देता है, और सबसे कम से कम महत्वपूर्ण अंक स्वाद में [[ आपको कामयाबी मिले ]] का चचेरा भाई है। बकेट सॉर्ट को तुलनाओं के साथ लागू किया जा सकता है और इसलिए इसे तुलनात्मक सॉर्ट एल्गोरिथ्म भी माना जा सकता है। [[एल्गोरिदम का विश्लेषण]] प्रत्येक बकेट को सॉर्ट करने के लिए उपयोग किए जाने वाले एल्गोरिदम, उपयोग की जाने वाली बकेट की संख्या और इनपुट समान रूप से वितरित है या नहीं, इस पर निर्भर करता है।
+[[File:Bucket sort 2.svg|right|frame|फिर, एलिमेंट्स को प्रत्येक बिन के भीतर सॉर्ट किया जाता है]]'''बकेट सॉर्ट''', या बिन सॉर्ट, एक [[छँटाई एल्गोरिथ्म|सॉर्टिंग अल्गोरिथम]] है जो ऐरे डेटा संरचना के एलिमेंट्स को कई बकेट में डिस्ट्रीब्यूट करके काम करता है। फिर प्रत्येक बकेट को अलग-अलग सॉर्ट किया जाता है, या तो एक अलग सॉर्टिंग एल्गोरिदम का उपयोग करके, या बकेट सॉर्टिंग एल्गोरिदम को रेकर्सिवली अप्लाई करके। यह एक डिस्ट्रीब्यूटिंग सॉर्ट है, [[कबूतरखाना प्रकार|पिजनहोल सॉर्ट]] का एक जनरलाईज़ेशन जो प्रति बकेट कई कीस को अलाव करता है, और मोस्ट-टू-लीस्ट सिग्नीफिकेंट डिजिट फ्लेवर में [[ आपको कामयाबी मिले |रेडिक्स सॉर्ट]] का कजिन है। बकेट सॉर्ट को कमपैरीजन के साथ लागू किया जा सकता है और इसलिए इसे कमपैरीजान सॉर्ट एल्गोरिथ्म भी माना जा सकता है। [[एल्गोरिदम का विश्लेषण|एल्गोरिदम nालिसिस]] प्रत्येक बकेट को सॉर्ट करने के लिए उपयोग किए जाने वाले एल्गोरिदम, उपयोग किये जाने वाले बकेट नंबर और इनपुट समान रूप से डिस्ट्रीब्यूट है या नहीं, इस पर निर्भर करता है।
 बकेट सॉर्ट इस प्रकार काम करता है:
-# शुरू में खाली बाल्टियों की एक श्रृंखला स्थापित करें।
+# इनीशिअली एम्प्टी बकेट की एक श्रृंखला सेट अप करें।
-# स्कैटर: प्रत्येक ऑब्जेक्ट को उसकी बकेट में डालते हुए, मूल सरणी पर जाएं।
+# स्कैटर: प्रत्येक ऑब्जेक्ट को उसकी बकेट में डालते हुए, ओरिजिनल ऐरे पर जाएं।
-# प्रत्येक गैर-खाली बाल्टी को क्रमबद्ध करें।
+# प्रत्येक नॉन-एम्प्टी बकेट को सॉर्ट करें।
-# इकट्ठा करें: बाल्टियों को क्रम से देखें और सभी तत्वों को मूल सरणी में वापस रखें।
+# गैदर: बकेट को आर्डर से देखें और सभी एलिमेंट्स को ओरिजिनल ऐरे में वापस रखें।
-==छद्मकोड==
+==स्यूडोकोड==
-  फ़ंक्शन BucketSort(array, k) है
+  '''function''' bucketSort(array, k) '''is'''
-      बकेट ← k खाली सूचियों की नई सारणी
+      buckets ← new array of k empty lists
-      एम ← 1 + सरणी में अधिकतम कुंजी मान
+      M ← 1 + the maximum key value in the array
-      i = 0 से लंबाई (सरणी) के लिए करें
+      '''for''' i = 0 '''to''' length(array) '''do'''
-          ''सरणी[i]'' को ''बाल्टी[तल(k × सारणी[i] / M)]'' में डालें
+          insert ''array[i]'' into ''buckets[floor(k × array[i] / M)]''
-      i = 0 से k के लिए
+      '''for''' i = 0 '''to''' k '''do'''
-          अगलासॉर्ट(बाल्टी[i])
+          nextSort(buckets[i])
-      बकेट[0], ...., बकेट[k] का संयोजन लौटाएँ
+      '''return''' the concatenation of buckets[0], ...., buckets[k]
-''मान लीजिए सारणी'' सॉर्ट किए जाने वाले सरणी को दर्शाती है और ''k'' उपयोग की जाने वाली बाल्टियों की संख्या को दर्शाती है। कोई भी सभी कुंजियों को एक बार दोहराकर [[रैखिक समय]] में अधिकतम कुंजी मान की गणना कर सकता है। [[फर्श समारोह]] का उपयोग फ़्लोटिंग नंबर को पूर्णांक में बदलने के लिए किया जाना चाहिए (और संभवतः डेटाटाइप की कास्टिंग भी)। फ़ंक्शन ''नेक्स्टसॉर्ट'' एक सॉर्टिंग फ़ंक्शन है जिसका उपयोग प्रत्येक बकेट को सॉर्ट करने के लिए किया जाता है। परंपरागत रूप से, [[[[चयन छांटना]]]] का उपयोग किया जाता है, लेकिन अन्य एल्गोरिदम का भी उपयोग किया जा सकता है, जैसे ''चयन सॉर्ट'' या ''[[ मर्ज़ सॉर्ट ]]''। ''बकेटसॉर्ट'' को ''नेक्स्टसॉर्ट'' के रूप में उपयोग करने से रेडिक्स सॉर्ट का एक रिश्तेदार उत्पन्न होता है; विशेष रूप से, मामला ''एन = 2'' [[जल्दी से सुलझाएं]] से मेल खाता है (हालांकि संभावित रूप से खराब धुरी विकल्पों के साथ)।
+मान लीजिए ऐरे सॉर्ट किए जाने वाले ऐरे को दर्शाती है और ''k'' उपयोग किये जाने वाले बकेट नंबर को दर्शाती है। कोई भी सभी कीस को एक बार दोहराकर [[रैखिक समय|लीनियर टाइम]] में अधिकतम की वैल्यू की गणना कर सकता है। [[फर्श समारोह|फ्लोर फंक्शन]] का उपयोग फ़्लोटिंग नंबर को इन्टिजर में बदलने के लिए किया जाना चाहिए (और संभवतः डेटाटाइप की कास्टिंग भी)। फ़ंक्शन नेक्स्टसॉर्ट एक सॉर्टिंग फ़ंक्शन है जिसका उपयोग प्रत्येक बकेट को सॉर्ट करने के लिए किया जाता है। कन्वेंशनली, [[चयन छांटना|इंसर्शन सॉर्ट]] का उपयोग किया जाता है, लेकिन अन्य एल्गोरिदम का भी उपयोग किया जा सकता है, जैसे सिलेक्शन सॉर्ट या [[ मर्ज़ सॉर्ट |मर्ज़ सॉर्ट]]। बकेटसॉर्ट को नेक्स्टसॉर्ट के रूप में उपयोग करने से रेडिक्स सॉर्ट का एक रिलेटिव उत्पन्न होता है; स्पेशल रूप से, केस ''n = 2'' [[जल्दी से सुलझाएं|क्विकसोर्ट]] से मेल खाता है (हालांकि संभावित रूप से खराब धुरी विकल्पों के साथ)।
-== विश्लेषण ==
+== एनालिसिस ==
-=== सबसे खराब स्थिति का विश्लेषण ===
+=== वर्स्ट-केस एनालिसिस ===
-जब इनपुट में कई कुंजियाँ होती हैं जो एक-दूसरे के करीब होती हैं (क्लस्टरिंग), तो उन तत्वों को एक ही बाल्टी में रखे जाने की संभावना होती है, जिसके परिणामस्वरूप कुछ बाल्टियों में औसत से अधिक तत्व होते हैं। सबसे खराब स्थिति तब होती है जब सभी तत्वों को एक ही बाल्टी में रखा जाता है। उदाहरण के लिए, समग्र प्रदर्शन तब प्रत्येक बकेट को सॉर्ट करने के लिए उपयोग किए जाने वाले एल्गोरिदम पर हावी होगा <math>O(n^2)</math> प्रविष्टि प्रकार या <math>O(n \log(n))</math> तुलना सॉर्ट एल्गोरिदम, जैसे मर्ज सॉर्ट।
+जब इनपुट में कई कीज़ होती हैं जो एक-दूसरे के क्लोज होती हैं (क्लस्टरिंग), तो उन एलिमेंट्स को एक ही बकेट में रखे जाने की संभावना होती है, जिसके परिणामस्वरूप कुछ बकेट में एवरेज से अधिक एलिमेंट होते हैं। सबसे खराब स्थिति तब होती है जब सभी एलिमेंट्स को एक ही बकेट में रखा जाता है। उदाहरण के लिए, इंसर्शन सॉर्ट तब ईच बकेट को सॉर्ट करने के लिए उपयोग किए जाने वाले एल्गोरिदम <math>O(n^2)</math> इंसर्शन सॉर्ट या <math>O(n \log(n))</math> कम्पैरिजन एल्गोरिदम पर हावी होगा, जैसे मर्ज सॉर्ट।
-=== औसत-मामला विश्लेषण ===
+=== एवरेज-केस एनालिसिस ===
-इस मामले पर विचार करें कि इनपुट समान रूप से वितरित है। पहला चरण, जो बकेट को प्रारंभ करना और सरणी में अधिकतम कुंजी मान ढूंढना है, में किया जा सकता है <math>O(n)</math> समय। यदि विभाजन और गुणा निरंतर समय में किया जा सकता है, तो प्रत्येक तत्व को उसकी बाल्टी में बिखेरने में भी लागत आती है <math>O(n)</math>. मान लें कि प्रत्येक बकेट को सॉर्ट करने के लिए इंसर्शन सॉर्ट का उपयोग किया जाता है, तो तीसरे चरण की लागत आती है <math>O(\textstyle \sum_{i=1}^k \displaystyle n_i^2)</math>, कहाँ <math>n_i</math> अनुक्रमित बाल्टी की लंबाई है <math>i</math>. चूँकि हम औसत समय, अपेक्षा से संबंधित हैं <math>E(n_i^2)</math> इसके बजाय मूल्यांकन करना होगा। होने देना <math>X_{ij}</math> वह यादृच्छिक चर हो <math>1</math> यदि तत्व <math>j</math> बाल्टी में रखा जाता है <math>i</math>, और <math>0</math> अन्यथा। अपने पास <math>n_i = \sum_{j=1}^n X_{ij}</math>. इसलिए,
+इस केस पर विचार करें कि इनपुट यूनिफोर्मली डिस्ट्रिब्यूटेड है। पहला स्टेप, जो बकेट को इनिशियलाइज़ करना और ऐरे में मैक्सिमम की वैल्यू ढूंढना <math>O(n)</math> समय में किया जा सकता है। यदि डिवीज़न और मल्टिप्लिकेशन निरंतर समय में किया जा सकता है, तो प्रत्येक एलिमेंट को उसकी बकेट में स्कैटरिंग करने में भी <math>O(n)</math> कॉस्ट आती है। मान लें कि प्रत्येक बकेट को सॉर्ट करने के लिए इंसर्शन सॉर्ट का उपयोग किया जाता है, तो तीसरे चरण की कॉस्ट <math>O(\textstyle \sum_{i=1}^k \displaystyle n_i^2)</math> आती है , जहाँ <math>n_i</math> इंडेक्स्ड बकेट की लंबाई <math>i</math> है। चूँकि हम एवरेज टाइम, एक्सपेक्टेशन <math>E(n_i^2)</math> से संबंधित हैं  इसके स्थान पर इवैल्यूएशन करना होगा। मान लीजिये <math>X_{ij}</math> वह रैंडम वेरिएबल <math>1</math> हो यदि एलिमेंट <math>j</math> बकेट <math>i</math> में रखा जाता है, अन्यथा <math>0</math> होगा। अपने पास <math>n_i = \sum_{j=1}^n X_{ij}</math> है। इसलिए,
 :<math>\begin{align}
@@ Line 43: / Line 43: @@
 & = 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{align} </math>
-अंतिम पंक्ति मामले में सारांश को अलग करती है <math>j=l</math> और मामला <math>j\neq l</math>. चूंकि किसी वस्तु को बाल्टी में वितरित करने का मौका है <math>i</math> है <math>1/k</math>, <math>X_{ij} </math> संभावना के साथ 1 है <math>1/k</math> और 0 अन्यथा.
+अंतिम पंक्ति केस में सममेशन <math>j=l</math> और केस <math>j\neq l</math> को अलग करती है। चूंकि बकेट <math>i</math> को वितरित की गई ऑब्जेक्ट का चांस <math>1/k</math> है, <math>X_{ij} </math> 1 प्रोबेबिलिटी <math>1/k</math> अन्यथा 0 है।
 :<math>E(X_{ij}^2) = 1^2\cdot \left(\frac{1}{k}\right) + 0^2\cdot \left(1-\frac{1}{k}\right) = \frac{1}{k}</math>
 :<math>E(X_{ij}X_{ik}) = 1\cdot \left(\frac{1}{k}\right)\left(\frac{1}{k}\right) = \frac{1}{k^2} </math>
-सारांश के साथ, यह होगा
+सममेशन के साथ, यह होगा
 :<math>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}</math>
-अंततः, जटिलता होगी <math>O\left(\sum_{i=1}^kE(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) </math>.
+अंततः, कम्प्लेक्सिटी  <math>O\left(\sum_{i=1}^kE(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) </math> होगी।
-बकेट सॉर्ट का अंतिम चरण, जो प्रत्येक बकेट में सभी सॉर्ट की गई वस्तुओं को संयोजित करना है, की आवश्यकता है <math>O(k)</math> समय। इसलिए, कुल जटिलता है <math>O\left(n+\frac{n^2}{k}+k\right)</math>. ध्यान दें कि यदि k को चुना गया है <math>k = \Theta(n)</math>, फिर बकेट सॉर्ट चलता है <math>O(n)</math> औसत समय, समान रूप से वितरित इनपुट दिया गया।<ref name="lfcs" />
+बकेट सॉर्ट का लास्ट स्टेप, जो प्रत्येक बकेट में सभी सॉर्ट किये गए ऑब्जेक्ट्स को कोंसटेनटिंग करना है, उन्हें <math>O(k)</math> समय की आवश्यकता है। इसलिए, कुल कॉम्पलेक्सिटी <math>O\left(n+\frac{n^2}{k}+k\right)</math> है। ध्यान दें कि यदि k को <math>k = \Theta(n)</math> चुना गया है, फिर बकेट सॉर्ट <math>O(n)</math> एवरेज टाइम पर चलता है, जहाँ समान रूप से डिस्ट्रीब्यूट इनपुट दिया गया। <ref name="lfcs" />
-==अनुकूलन==
+==ऑप्टिमाइजेशन==
-एक सामान्य अनुकूलन यह है कि बकेट के अवर्गीकृत तत्वों को पहले मूल सरणी में वापस रखा जाए, फिर संपूर्ण सरणी पर सम्मिलन सॉर्ट चलाया जाए; क्योंकि प्रविष्टि प्रकार का रनटाइम इस पर आधारित होता है कि प्रत्येक तत्व अपनी अंतिम स्थिति से कितनी दूर है, तुलनाओं की संख्या अपेक्षाकृत कम रहती है, और सूची को स्मृति में सन्निहित रूप से संग्रहीत करके स्मृति पदानुक्रम का बेहतर उपयोग किया जाता है।<ref>Corwin, E. and Logar, A. "Sorting in linear time — variations on the bucket sort". ''Journal of Computing Sciences in Colleges'', 20, 1, pp.197–202. October 2004.</ref>
+एक सामान्य ऑप्टिमाइजेशन यह है कि बकेट के अनसोर्टेड एलिमेंट्स को पहले ओरिजिनल ऐरे में वापस रखा जाए, फिर संपूर्ण ऐरे पर इंसर्शन सॉर्ट चलाया जाए; क्योंकि इंसर्शन सॉर्ट का रनटाइम इस पर आधारित होता है कि प्रत्येक एलिमेंट अपनी फाइनल पोजीशन से कितनी दूर है, कमपैरीजन नंबर रेलटीवेली कम रहती है, और सूची को मेमोरी में कंटिगोस्ली स्टोर करके मेमोरी हायरार्की का बेहतर उपयोग किया जाता है। <ref>Corwin, E. and Logar, A. "Sorting in linear time — variations on the bucket sort". ''Journal of Computing Sciences in Colleges'', 20, 1, pp.197–202. October 2004.</ref>
-यदि इनपुट वितरण ज्ञात है या अनुमान लगाया जा सकता है, तो अक्सर ऐसी बाल्टियाँ चुनी जा सकती हैं जिनमें स्थिर घनत्व होता है (केवल स्थिर आकार के बजाय)। यह अनुमति देता है <math>O(n)</math> समान रूप से वितरित इनपुट के बिना भी औसत समय जटिलता।
+यदि इनपुट डिस्ट्रीब्यूटिंग ज्ञात है या एस्टीमेट किया जा सकता है, तो प्रायः ऐसी बकेट चुनी जा सकती हैं जिनमें कांस्टेंट डेंसिटी होता है (केवल कांस्टेंट साइज के स्थान पर)। यह समान रूप से वितरित इनपुट के बिना भी <math>O(n)</math> एवरेज टाइम कॉम्पलेक्सिटी की अनुमति देता है।
 == वेरिएंट ==
 ===जेनेरिक बकेट सॉर्ट===
-बकेट सॉर्ट का सबसे आम संस्करण शून्य और कुछ अधिकतम मान एम के बीच एन संख्यात्मक इनपुट की एक सूची पर काम करता है और मूल्य सीमा को प्रत्येक आकार एम/एन के एन बकेट में विभाजित करता है। यदि प्रत्येक बकेट को सम्मिलन सॉर्ट का उपयोग करके सॉर्ट किया जाता है, तो सॉर्ट को अपेक्षित रैखिक समय में चलते हुए दिखाया जा सकता है (जहां सभी संभावित इनपुट पर औसत लिया जाता है)।<ref>[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7}}. Section 8.4: Bucket sort, pp.174&ndash;177.</ref> हालाँकि, इस प्रकार का प्रदर्शन क्लस्टरिंग के साथ ख़राब हो जाता है; यदि कई मान एक साथ आते हैं, तो वे सभी एक ही बाल्टी में गिर जाएंगे और धीरे-धीरे क्रमबद्ध हो जाएंगे। यह मानते हुए कि इनपुट एक यादृच्छिक प्रक्रिया द्वारा उत्पन्न होता है जो अंतराल [0,1) पर तत्वों को समान रूप से वितरित करता है, इस प्रदर्शन में गिरावट को मूल बकेट सॉर्ट एल्गोरिदम में टाला जाता है।<ref name="lfcs">{{cite book|title=[[Introduction to Algorithms]]|author=Thomas H. Cormen|author-link=Thomas H. Cormen|author2=Charles E. Leiserson|author2-link=Charles E. Leiserson|author3=Ronald L. Rivest|author3-link=Ronald L. Rivest|author4=Clifford Stein|author4-link=Clifford Stein|name-list-style=amp|quote=Bucket sort runs in linear time on the average. Like counting sort, bucket sort is fast because it assumes something about the input. Whereas counting sort assumes that the input consists of integers in a small range, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval ''[0,1)''. The idea of bucket sort is to divide the interval ''[0, 1)'' into ''n'' equal-sized subintervals, or buckets, and then distribute the ''n'' input numbers into the buckets. Since the inputs are uniformly distributed over ''[0, 1)'', we don't expect many numbers to fall into each bucket. To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing the elements in each.}}</ref>
+बकेट सॉर्ट का सबसे सामान्य वैरिएंट शून्य और कुछ मैक्सिमम वैल्यू m के बीच n न्यूमेरिक इनपुट की एक सूची पर काम करता है और वैल्यू रेंज को प्रत्येक साइज m/n के n बकेट में डिवाइड करता है। यदि प्रत्येक बकेट को इंसर्शन सॉर्ट का उपयोग करके सॉर्ट किया जाता है, तो सॉर्ट को एक्सपेक्टेड लीनियर टाइम में चलते हुए दिखाया जा सकता है (जहां सभी पॉसिबल इनपुट पर औसत लिया जाता है)। <ref>[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7}}. Section 8.4: Bucket sort, pp.174&ndash;177.</ref> हालाँकि, इस प्रकार का परफॉरमेंस क्लस्टरिंग के साथ डीग्रेड हो जाता है; यदि कई वैल्यू एक साथ आती हैं, तो वे सभी एक ही बकेट में गिर जाएंगे और धीरे-धीरे सॉर्ट हो जाएंगे। यह मानते हुए कि इनपुट एक रैंडम प्रोसेस द्वारा उत्पन्न होता है जो इंटरवल [0,1) पर एलिमेंट्स को यूनिफोर्मली डिस्ट्रीब्यूट करता है, इस परफॉरमेंस डिग्रडेशन को ओरिजिनल बकेट सॉर्ट एल्गोरिदम में टाला जाता है। <ref name="lfcs">{{cite book|title=[[Introduction to Algorithms]]|author=Thomas H. Cormen|author-link=Thomas H. Cormen|author2=Charles E. Leiserson|author2-link=Charles E. Leiserson|author3=Ronald L. Rivest|author3-link=Ronald L. Rivest|author4=Clifford Stein|author4-link=Clifford Stein|name-list-style=amp|quote=Bucket sort runs in linear time on the average. Like counting sort, bucket sort is fast because it assumes something about the input. Whereas counting sort assumes that the input consists of integers in a small range, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval ''[0,1)''. The idea of bucket sort is to divide the interval ''[0, 1)'' into ''n'' equal-sized subintervals, or buckets, and then distribute the ''n'' input numbers into the buckets. Since the inputs are uniformly distributed over ''[0, 1)'', we don't expect many numbers to fall into each bucket. To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing the elements in each.}}</ref>
 ===प्रोक्समैपसॉर्ट===
-{{Main article|Proxmap sort}}
+{{Main article|प्रोक्समैप सॉर्ट}}
-जैसा कि ऊपर बताया गया है, जेनेरिक बकेट सॉर्ट के समान, ProxmapSort एक मैप कुंजी फ़ंक्शन के उपयोग के माध्यम से कुंजियों की एक सरणी को उपसरणी में विभाजित करके काम करता है जो कुंजियों पर आंशिक क्रम को संरक्षित करता है; चूंकि प्रत्येक कुंजी को उसके उपसरणी में जोड़ा जाता है, उस उपसरणी को क्रमबद्ध रखने के लिए सम्मिलन सॉर्ट का उपयोग किया जाता है, जिसके परिणामस्वरूप ProxmapSort पूरा होने पर संपूर्ण सरणी क्रमबद्ध क्रम में होती है। ProxmapSort डेटा को क्रमबद्ध क्रम में लगभग उसी स्थान पर रखने के लिए मैप कुंजी के उपयोग में बकेट सॉर्ट से भिन्न होता है, जो कुंजियों का एक प्रॉक्समैप - एक निकटता मैपिंग - तैयार करता है।
+जैसा कि ऊपर बताया गया है, जेनेरिक बकेट सॉर्ट के समान, प्रोक्समैपसॉर्ट एक मैप के फ़ंक्शन के उपयोग के माध्यम से कीस के एक ऐरे को सबऐरे में डिवाइड करके काम करता है जो कीस पर पार्शियल ऑर्डरिंग को संरक्षित करता है; चूंकि प्रत्येक कीज़ को उसके सबऐरे में जोड़ा जाता है, उस सबऐरे को सॉर्ट रखने के लिए इंसर्शन सॉर्ट का उपयोग किया जाता है, जिसके परिणामस्वरूप प्रोक्समैपसॉर्ट पूरा होने पर संपूर्ण ऐरे सॉर्ट क्रम में होती है। प्रोक्समैपसॉर्ट डेटा को सॉर्ट क्रम में लगभग उसी स्थान पर रखने के लिए मैप कीज़ के उपयोग में बकेट सॉर्ट से भिन्न होता है, जो कीस का एक प्रॉक्समैप - एक प्रोक्सिमिटी मैपिंग - तैयार करता है।
 ===हिस्टोग्राम सॉर्ट===
-बकेट सॉर्ट का एक अन्य प्रकार जिसे हिस्टोग्राम सॉर्ट या [[ गिनती क्रम ]] के रूप में जाना जाता है, एक प्रारंभिक पास जोड़ता है जो गिनती सरणी का उपयोग करके प्रत्येक बकेट में आने वाले तत्वों की संख्या की गणना करता है।<ref>[https://xlinux.nist.gov/dads/HTML/histogramSort.html NIST's Dictionary of Algorithms and Data Structures: histogram sort]</ref> इस जानकारी का उपयोग करके, सरणी मानों को एक्सचेंजों के अनुक्रम द्वारा बाल्टी के अनुक्रम में व्यवस्थित किया जा सकता है, जिससे बाल्टी भंडारण के लिए कोई जगह नहीं बचती है।{{Not in source|date=September 2020}}
+बकेट सॉर्ट का एक अन्य प्रकार जिसे हिस्टोग्राम सॉर्ट या [[ गिनती क्रम |काउंटिंग सॉर्ट]] के रूप में जाना जाता है, एक इनिशियल पास जोड़ता है जो काउंटिंग ऐरे का उपयोग करके प्रत्येक बकेट में आने वाले एलिमेंट्स की नंबर की गणना करता है। <ref>[https://xlinux.nist.gov/dads/HTML/histogramSort.html NIST's Dictionary of Algorithms and Data Structures: histogram sort]</ref> इस इनफार्मेशन का उपयोग करके, ऐरे वैल्यू को एक्सचेंजों के सीक्वेंस द्वारा बकेट के सीक्वेंस में अररेंज किया जा सकता है, जिससे बकेट स्टोरेज के लिए कोई स्पेस नहीं बचती है।
-===डाकिया का प्रकार===<!-- This section is linked from [[Radix sort]] -->
+===पोस्टमैन सॉर्ट===
-पोस्टमैन का सॉर्ट बकेट सॉर्ट का एक प्रकार है जो तत्वों की पदानुक्रमित संरचना का लाभ उठाता है, जिसे आमतौर पर विशेषताओं के एक सेट द्वारा वर्णित किया जाता है। यह डाकघरों में पत्र-छँटाई मशीनों द्वारा उपयोग किया जाने वाला एल्गोरिदम है: मेल को पहले घरेलू और अंतर्राष्ट्रीय के बीच क्रमबद्ध किया जाता है; फिर राज्य, प्रांत या क्षेत्र द्वारा; फिर गंतव्य डाकघर से; फिर मार्गों आदि द्वारा। चूँकि कुंजियों की एक-दूसरे से तुलना नहीं की जाती है, इसलिए छँटाई का समय O(''cn'') है, जहाँ ''c'' कुंजी के आकार और बकेट की संख्या पर निर्भर करता है। यह मूलांक प्रकार के समान है जो ऊपर से नीचे, या सबसे महत्वपूर्ण अंक पहले काम करता है।<ref>{{Cite web|url=http://www.rrsd.com/psort/cuj/cuj.htm|title = Robert Ramey Software Development}}</ref>
+पोस्टमैन सॉर्ट बकेट सॉर्ट का एक प्रकार है जो एलिमेंट्स की हायरार्चिकाल स्ट्रक्चर का लाभ उठाता है, जिसे सामान्यतः एट्रिब्यूट के एक सेट द्वारा वर्णित किया जाता है। यह डाकघरों में लेटर-सॉर्टिंग मशीनों द्वारा उपयोग किया जाने वाला एल्गोरिदम है: मेल को पहले डोमेस्टिक और इंटरनेशनल के बीच सॉर्ट किया जाता है; फिर स्टेट, प्रोविंस या टेरिटरी द्वारा; फिर डेस्टिनेशन पोस्टऑफिस से; फिर रुट्स आदि द्वारा। चूँकि कीस की एक-दूसरे से कम्पेरिज़न नहीं की जाती है, इसलिए सॉर्टिंग टाइम O(''cn'') है, जहाँ ''c'' की के साइज और बकेट के नंबर पर निर्भर करता है। यह मूलांक प्रकार के समान है जो ऊपर से नीचे, या मोस्ट सिग्नीफिकेंट डिजिट पहले काम करता है। <ref>{{Cite web|url=http://www.rrsd.com/psort/cuj/cuj.htm|title = Robert Ramey Software Development}}</ref>
-===फेरबदल प्रकार===<!-- This section is linked from [[J sort]] -->
+===शफल सॉर्ट===
-फेरबदल प्रकार<ref>[https://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3 A revolutionary new sort from John Cohen Nov 26, 1997]</ref> बकेट सॉर्ट का एक प्रकार है जो सॉर्ट किए जाने वाले n आइटमों के पहले 1/8 को हटाकर शुरू होता है, उन्हें पुनरावर्ती रूप से सॉर्ट करता है, और उन्हें एक सरणी में रखता है। इससे n/8 बाल्टियाँ बनती हैं जिनमें शेष 7/8 वस्तुएँ वितरित की जाती हैं। फिर प्रत्येक बाल्टी को क्रमबद्ध किया जाता है, और बाल्टी को एक क्रमबद्ध सरणी में संयोजित किया जाता है।
+शफल सॉर्ट <ref>[https://groups.google.com/group/fido7.ru.algorithms/msg/26084cdb04008ab3 A revolutionary new sort from John Cohen Nov 26, 1997]</ref> बकेट सॉर्ट का एक प्रकार है जो सॉर्ट किए जाने वाले n आइटमों के पहले 1/8 को हटाकर प्रारम्भ होता है, उन्हें पुनरावर्ती रूप से सॉर्ट करता है, और उन्हें एक ऐरे में रखता है। इससे n/8 बकेट बनती हैं जिनमें शेष 7/8 आइटम डिस्ट्रीब्यूट की जाती हैं। फिर प्रत्येक बकेट को सॉर्ट किया जाता है, और बकेट को एक सॉर्ट ऐरे में कोंसटेनटिंग किया जाता है।
-==अन्य सॉर्टिंग एल्गोरिदम के साथ तुलना==
+==अन्य सॉर्टिंग एल्गोरिदम के साथ कम्पेरिज़न==
-बकेट सॉर्ट को गिनती सॉर्ट के सामान्यीकरण के रूप में देखा जा सकता है; वास्तव में, यदि प्रत्येक बाल्टी का आकार 1 है तो बाल्टी सॉर्ट गिनती सॉर्ट में बदल जाता है। बकेट सॉर्ट का परिवर्तनशील बकेट आकार इसे O(M) मेमोरी के बजाय O(n) मेमोरी का उपयोग करने की अनुमति देता है, जहां M विशिष्ट मानों की संख्या है; बदले में, यह प्रकार के O(n + M) सबसे खराब स्थिति वाले व्यवहार की गिनती करना छोड़ देता है।
+बकेट सॉर्ट को काउंटिंग सॉर्ट के जनरलाईज़ेशन के रूप में देखा जा सकता है; वास्तव में, यदि प्रत्येक बकेट का साइज 1 है तो बकेट सॉर्ट काउंटिंग सॉर्ट में बदल जाता है। बकेट सॉर्ट का वेरिएबल बकेट साइज इसे O(M) मेमोरी के स्थान पर O(n) मेमोरी का उपयोग करने की अनुमति देता है, जहां M विशिष्ट वैल्यू नंबर है; बदले में, यह प्रकार के O(n + M) सबसे खराब स्थिति वाले बिहेवियर की काउंटिंग करना छोड़ देता है।
-दो बकेट के साथ बकेट सॉर्ट प्रभावी रूप से क्विकसॉर्ट का एक संस्करण है जहां पिवट मान को हमेशा मूल्य सीमा के मध्य मान के रूप में चुना जाता है। जबकि यह विकल्प समान रूप से वितरित इनपुट के लिए प्रभावी है, क्विकॉर्ट में पिवट चुनने के अन्य साधन जैसे यादृच्छिक रूप से चयनित पिवोट इसे इनपुट वितरण में क्लस्टरिंग के प्रति अधिक प्रतिरोधी बनाते हैं।
+दो बकेट के साथ बकेट सॉर्ट एफ्फेक्टिवेली क्विकसॉर्ट का एक वैरिएंट है जहां पिवट वैल्यू को हमेशा वैल्यू रेंज के मध्य वैल्यू के रूप में चुना जाता है। जबकि यह विकल्प समान रूप से डिस्ट्रीब्यूट इनपुट के लिए प्रभावी है, क्विकॉर्ट में पिवट चुनने के अन्य साधन जैसे यादृच्छिक रूप से सिलेक्शनित पिवोट इसे इनपुट डिस्ट्रीब्यूटिंग में क्लस्टरिंग के प्रति अधिक रेसिस्टेंट बनाते हैं।
-एन-वे [[मर्ज़ सॉर्ट]] एल्गोरिथ्म भी सूची को एन उपसूचियों में वितरित करने और प्रत्येक को क्रमबद्ध करने से शुरू होता है; हालाँकि, मर्जसॉर्ट द्वारा बनाई गई उपसूचियों में ओवरलैपिंग वैल्यू रेंज होती हैं और इसलिए इन्हें बकेट सॉर्ट की तरह सरल संयोजन द्वारा पुनः संयोजित नहीं किया जा सकता है। इसके बजाय, उन्हें मर्ज एल्गोरिदम द्वारा इंटरलीव किया जाना चाहिए। हालाँकि, यह अतिरिक्त व्यय सरल बिखराव चरण और यह सुनिश्चित करने की क्षमता से संतुलित होता है कि प्रत्येक उपसूची एक ही आकार की है, जो एक अच्छी सबसे खराब स्थिति के लिए समयबद्धता प्रदान करती है।
+n-वे [[मर्ज़ सॉर्ट]] एल्गोरिथ्म भी सूची को n उपसूचियों में डिस्ट्रीब्यूट करने और प्रत्येक को सॉर्ट करने से प्रारम्भ होता है; हालाँकि, मर्जसॉर्ट द्वारा बनाई गई सबलिस्ट में ओवरलैपिंग वैल्यू रेंज होती हैं और इसलिए इन्हें बकेट सॉर्ट की तरह सिंपल कॉन्कटेनशन द्वारा पुनः कोंसटेनटिंग नहीं किया जा सकता है। इसके स्थान पर, उन्हें मर्ज एल्गोरिदम द्वारा इंटरलीव किया जाना चाहिए। हालाँकि, यह एडेड एक्सपेंस सिम्पलर स्कैटर फेज और यह इनश्योर करने की क्षमता से संतुलित होता है कि प्रत्येक सबलिस्ट एक ही साइज की है, जो एक अच्छी वर्स्ट-केस के लिए टाइम बाउंड प्रदान करती है।
-टॉप-डाउन रेडिक्स सॉर्ट को बकेट सॉर्ट के एक विशेष मामले के रूप में देखा जा सकता है, जहां मानों की सीमा और बकेट की संख्या दोनों दो की घात के लिए बाध्य हैं। नतीजतन, प्रत्येक बाल्टी का आकार भी दो की शक्ति है, और प्रक्रिया को पुनरावर्ती रूप से लागू किया जा सकता है। यह दृष्टिकोण बिखराव चरण को तेज कर सकता है, क्योंकि हमें केवल इसकी बाल्टी निर्धारित करने के लिए प्रत्येक तत्व के बिट प्रतिनिधित्व के उपसर्ग की जांच करने की आवश्यकता है।
+टॉप-डाउन रेडिक्स सॉर्ट को बकेट सॉर्ट के एक स्पेशल केस के रूप में देखा जा सकता है, जहां वैल्यू की रेंज और बकेट के नंबर दोनों दो की पावर के लिए बाध्य हैं। नतीजतन, प्रत्येक बकेट का साइज भी दो की पावर है, और प्रोसीजर को रिकर्सिवली रूप से लागू किया जा सकता है। यह एप्रोच स्कैटर फेज को एक्सेलेरेट कर सकता है, क्योंकि हमें केवल इसकी बकेट डेटरमाइन करने के लिए प्रत्येक एलिमेंट के बिट रिप्रजेंटेशन के उपसर्ग की जांच करने की आवश्यकता है।
 ==संदर्भ==

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort Slowsort Stooge sort Bogosort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort

Anonymous

Search

बकेट सॉर्ट: Difference between revisions

Namespaces

More

Page actions

Revision as of 01:03, 2 August 2023

Contents

स्यूडोकोड