बकेट सॉर्ट

बकेट सॉर्ट

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)$

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

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

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

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

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

स्यूडोकोड

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)$ एवरेज टाइम पर चलता है, जहाँ समान रूप से डिस्ट्रीब्यूट इनपुट दिया गया।

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

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

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

वेरिएंट

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

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

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

Main article: प्रोक्समैप सॉर्ट

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

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

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

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

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

शफल सॉर्ट

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

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

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

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

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

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

संदर्भ

• 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