बकेट सॉर्ट

बकेट सॉर्ट

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

File:Bucket sort 1.svg

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

File:Bucket sort 2.svg

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

बकेट सॉर्ट, या बिन सॉर्ट, एक सॉर्टिंग अल्गोरिथम है जो ऐरे डेटा संरचना के एलिमेंट्स को कई बकेट में डिस्ट्रीब्यूट करके काम करता है। फिर प्रत्येक बकेट को अलग-अलग सॉर्ट किया जाता है, या तो एक अलग सॉर्टिंग एल्गोरिदम का उपयोग करके, या बकेट सॉर्टिंग एल्गोरिदम को रेकर्सिवली अप्लाई करके। यह एक डिस्ट्रीब्यूटिंग सॉर्ट है, पिजनहोल सॉर्ट का एक जनरलाईज़ेशन जो प्रति बकेट कई कीस को अलाव करता है, और मोस्ट-टू-लीस्ट सिग्नीफिकेंट डिजिट फ्लेवर में रेडिक्स सॉर्ट का कजिन है। बकेट सॉर्ट को कमपैरीजन के साथ लागू किया जा सकता है और इसलिए इसे कमपैरीजान सॉर्ट एल्गोरिथ्म भी माना जा सकता है। एल्गोरिदम 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$ को वितरित की गई ऑब्जेक्ट का चांस ${\displaystyle }$