बकेट सॉर्ट एल्गोरिथ्म (Java, Python, सी/C++ कोड उदाहरण)
सारा चेन
बकेट सॉर्ट क्या है?
बकेट सॉर्ट, जिसे अक्सर बिन सॉर्ट कहा जाता है, एक तुलनात्मक सॉर्ट विधि है जो एक अनसॉर्टेड सरणी को इनपुट के रूप में स्वीकार करती है और परिणामस्वरूप एक सॉर्टेड सरणी बनाती है। यह विधि तत्वों को कई बकेट में वितरित करके और उनमें से प्रत्येक बकेट को किसी भी सॉर्टिंग एल्गोरिदम जैसे कि इंसर्शन सॉर्ट द्वारा व्यक्तिगत रूप से सॉर्ट करके काम करती है। फिर सभी बकेट को एक सॉर्टेड सरणी बनाने के लिए एक साथ मिला दिया जाता है।
बकेट सॉर्ट का उपयोग आमतौर पर तब किया जाता है जब तत्व-
- फ़्लोटिंग-पॉइंट मान
- एक सीमा पर समान रूप से वितरित
बकेट सॉर्ट की समय जटिलता उपयोग की गई बकेट की संख्या और इनपुट वितरण की एकरूपता पर निर्भर करती है। जबकि विभिन्न सॉर्टिंग एल्गोरिदम जैसे शैल सॉर्ट, मर्ज सॉर्ट, हीपसॉर्ट, और जल्दी से सुलझाएं O(n*logn) की सर्वोत्तम समय जटिलता प्राप्त कर सकता है, बकेट सॉर्टिंग एल्गोरिदम इसे रैखिक समय जटिलता या O(n) में प्राप्त कर सकता है।
बकेट सॉर्ट स्कैटर-गैदर दृष्टिकोण का अनुसरण करता है। इस दृष्टिकोण को लागू करते हुए, तत्वों को संबंधित बकेट में बिखेर दिया जाता है, बकेट में सॉर्ट किया जाता है, और अंतिम चरण के रूप में सॉर्टेड ऐरे बनाने के लिए इकट्ठा किया जाता है। इस स्कैटर-गैदर दृष्टिकोण पर निम्नलिखित अनुभाग में चर्चा की गई है
बिखराव-एकत्रीकरण-दृष्टिकोण
बड़े पैमाने पर जटिल समस्याओं को हल करना कभी-कभी चुनौतीपूर्ण हो सकता है। बिखराव-एकत्रित दृष्टिकोण पूरे डेटा सेट को क्लस्टर में विभाजित करके ऐसी समस्याओं को हल करने का प्रयास करता है। फिर प्रत्येक क्लस्टर को अलग से संबोधित किया जाता है और अंतिम उत्तर प्राप्त करने के लिए सब कुछ वापस एक साथ लाया जाता है।
इस प्रकार बकेट सॉर्टिंग एल्गोरिदम स्कैटर-गैदर विधि को क्रियान्वित करता है:
बकेट सॉर्ट कैसे काम करता है
बकेट सॉर्ट का मूल कार्य सिद्धांत इस प्रकार है:
- खाली बकेट का एक सेट बनाया जाता है। अलग-अलग नीतियों के आधार पर, बकेट की संख्या अलग-अलग हो सकती है।
- इनपुट ऐरे से, प्रत्येक तत्व को उसके संगत बकेट में डालें।
- उन बाल्टियों को अलग-अलग छांटें।
- एकल आउटपुट सारणी बनाने के लिए क्रमबद्ध बकेटों को संयोजित करें।
कार्य के विस्तृत चरण निम्नलिखित अनुभागों में दिए गए हैं।
छद्म कोड
Start Create N empty buckets For each array element: Calculate bucket index Put that element into the corresponding bucket For each bucket: Sort elements within each bucket Merge all the elements from each bucket Output the sorted array End
विधि 1: फ्लोटिंग-पॉइंट के लिए बकेट सॉर्ट एल्गोरिदम Numbers
0.0 से 1.0 की सीमा के भीतर फ्लोटिंग पॉइंट संख्याओं के लिए बकेट सॉर्टिंग एल्गोरिदम:
चरण 1) दस(10) खाली बकेट बनाएँ, ताकि पहली बकेट में [0.0, 0.1) की सीमा के भीतर संख्याएँ हों। फिर दूसरी बकेट में [0.1, 0.2) के भीतर संख्याएँ होंगी, और इसी तरह।
चरण 2) प्रत्येक सरणी तत्व के लिए:
-
a. सूत्र का उपयोग करके बकेट इंडेक्स की गणना करें:
बकेट इंडेक्स = no_of_buckets * array_element
-
b. बकेट में तत्व डालें[bucket_index]
चरण 3) सम्मिलन सॉर्ट का उपयोग करके प्रत्येक बकेट को अलग-अलग सॉर्ट करें।
चरण 4) सभी बकेटों को एक एकल सारणी में संयोजित करें।
आइए बकेट सॉर्ट का एक उदाहरण देखें। इस उदाहरण के लिए, हम बकेट सॉर्ट एल्गोरिथ्म का उपयोग करके निम्नलिखित सरणी को सॉर्ट करेंगे-
चरण 1) सबसे पहले, हम 10 खाली बकेट बनाएंगे। पहली बकेट में [0.0, 0.1) के बीच की संख्याएँ होंगी। फिर दूसरी बकेट में [0.1, 0.2) के बीच की संख्याएँ होंगी और इसी तरह आगे भी।
चरण 2) प्रत्येक ऐरे तत्व के लिए, हम बकेट इंडेक्स की गणना करेंगे और तत्व को उस बकेट में रखेंगे।
बकेट इंडेक्स की गणना निम्न सूत्र का उपयोग करके की जा सकती है:
bucket_index = no_of_buckets*array_element
बकेट इंडेक्स गणना:
एक) 0.78
बकेट_इंडेक्स = बकेट की संख्या*एरे_तत्व
= 10 * 0.78
= 7.8
इसलिए, तत्व 0.78 को बकेट[फ़्लोर(7.8)] या बकेट[7] पर संग्रहीत किया जाएगा।
बी) 0.17
bucket_index = no_of_buckets * सरणी तत्व
= 10 * 0.17
= 1.7
सरणी तत्व 0.17 को बकेट[फ़्लोर(1.7)] या बकेट[1] पर संग्रहीत किया जाएगा।
ग) 0.39
bucket_index = no_of_buckets * सरणी तत्व
= 10 * 0.39
= 3.9
0.39 को बकेट[फ़्लोर(3.9)] या बकेट[3] पर संग्रहीत किया जाएगा.
सभी ऐरे तत्वों पर पुनरावृत्ति करने के बाद, बकेट निम्नलिखित होंगे:
चरण 3) फिर, प्रत्येक बकेट को इन्सर्टेशन सॉर्ट का उपयोग करके सॉर्ट किया जाएगा। सॉर्टिंग ऑपरेशन के बाद, आउटपुट होगा:
चरण 4) अंतिम चरण में, बकेट को एक एकल सरणी में संयोजित किया जाएगा। वह सरणी इनपुट का क्रमबद्ध परिणाम होगा।
प्रत्येक बकेट को आउटपुट ऐरे से संयोजित किया जाएगा। उदाहरण के लिए- दूसरे बकेट तत्वों का संयोजन:
अंतिम बकेट तत्वों का संयोजन निम्नलिखित होगा:
संयोजन के बाद, परिणामी सरणी वांछित क्रमबद्ध सरणी होगी।
सी/ में बकेट सॉर्ट प्रोग्रामC++
इनपुट:
//Bucket Sort Program in C/C++
//For not having integer parts
#include <bits/stdc++.h>
#define BUCKET_SIZE 10
using namespace std;
void bucketSort(float input[], int array_size)
{
vector <float>bucket[BUCKET_SIZE];
for (int i = 0; i < array_size; i++) {
int index = BUCKET_SIZE*input[i];
bucket[index].push_back(input[i]);
}
for (int i = 0; i < BUCKET_SIZE; i++)
sort(bucket[i].begin(), bucket[i].end());
int out_index = 0;
for (int i = 0; i < BUCKET_SIZE; i++)
for (int j = 0; j < bucket[i].size(); j++)
input[out_index++] = bucket[i][j];
}
int main()
{
float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69};
int array_size = sizeof(input)/sizeof(input[0]);
bucketSort(input, array_size);
cout <<"Sorted Output: \n";
for (int i = 0; i< array_size; i++)
cout<<input[i]<<" ";
return 0;
}
आउटपुट:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
बकेट सॉर्ट कार्यक्रम Python
इनपुट:
# Bucket Sort Program in Python
# For not having integer parts
def bucketSort(input):
output = []
bucket_size = 10
for bucket in range(bucket_size):
output.append([])
for element in input:
index = int(bucket_size * element)
output[index].append(element)
for bucket in range(bucket_size):
output[bucket] = sorted(output[bucket])
out_index = 0
for bucket in range(bucket_size):
for element in range(len(output[bucket])):
input[out_index] = output[bucket][element]
out_index += 1
return input
input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69]
print("Sorted Output:")
print(bucketSort(input))
आउटपुट:
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
बकेट सॉर्ट इन Java
इनपुट:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
private static final int BUCKET_SIZE = 10;
public static void bucketSort(float[] input, int arraySize) {
List <
Float >
[] bucket = new ArrayList[BUCKET_SIZE];
for (int i = 0; i < arraySize; i++) {
int index = (int)(BUCKET_SIZE * input[i]);
if (bucket[index] == null) {
bucket[index] = new ArrayList < >
();
}
bucket[index].add(input[i]);
}
for (int i = 0; i < BUCKET_SIZE; i++) {
if (bucket[i] != null) {
Collections.sort(bucket[i]);
}
}
int outIndex = 0;
for (int i = 0; i < BUCKET_SIZE; i++) {
if (bucket[i] != null) {
for (float value: bucket[i]) {
input[outIndex++] = value;
}
}
}
}
public static void main(String[] args) {
float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f};
int arraySize = input.length;
bucketSort(input, arraySize);
System.out.println("Sorted Output:");
for (int i = 0; i < arraySize; i++) {
System.out.print(input[i]+" ");
}
}
}
आउटपुट:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
विधि 2: पूर्णांक तत्वों के लिए बकेट सॉर्ट एल्गोरिथ्म
[0.0, 1.0] सीमा से परे संख्याओं वाले इनपुट के लिए बकेट सॉर्ट एल्गोरिथ्म पिछले वाले से थोड़ा अलग है कलन विधिइस मामले के लिए आवश्यक कदम इस प्रकार हैं-
चरण 1) अधिकतम और न्यूनतम तत्व ज्ञात करें।
चरण 2) बकेट की संख्या n चुनें, और उन बकेट को रिक्त के रूप में आरंभ करें।
चरण 3) सूत्र का उपयोग करके प्रत्येक बकेट की सीमा या अवधि की गणना करें:
span = (maximum - minimum)/n
चरण 4) प्रत्येक सरणी तत्व के लिए:
-
1.बकेट इंडेक्स की गणना करें:
bucket_index = (element - minimum)/span-
2.तत्व को बकेट[bucket_index] में डालें
चरण 5) प्रत्येक बकेट को सम्मिलन सॉर्ट का उपयोग करके सॉर्ट करें।
चरण 6) सभी बकेटों को एक एकल सारणी में संयोजित करें।
आइए इस बकेट सॉर्ट एल्गोरिथ्म का एक उदाहरण देखें। इस उदाहरण के लिए, हम बकेट सॉर्ट एल्गोरिथ्म का उपयोग करके निम्नलिखित सरणी को सॉर्ट करेंगे-
चरण 1) पहले चरण में, दिए गए सरणी के अधिकतम और न्यूनतम तत्वों को खोजने की आवश्यकता है। इस उदाहरण के लिए, अधिकतम 24 है और न्यूनतम 1 है।
चरण 2) अब, हमें खाली बकेट की संख्या चुननी है, n. इस उदाहरण में, हम 5 बकेट लेंगे। फिर हम उन्हें खाली के रूप में आरंभ करेंगे।
चरण 3) प्रत्येक बकेट की अवधि की गणना निम्नलिखित सूत्र द्वारा की जानी चाहिए:
span = (maximum-minimum)/n = (24-1)/5 = 4;
इसलिए, पहली बकेट में [0, 5) की सीमा के भीतर की संख्याएँ होंगी। दूसरी बकेट में [5, 10) के भीतर की संख्याएँ होंगी और इसी तरह आगे भी।
चरण 4) प्रत्येक ऐरे तत्व के लिए, हम बकेट इंडेक्स की गणना करेंगे और तत्व को उस बकेट में रखेंगे। बकेट इंडेक्स की गणना सूत्र का उपयोग करके की जा सकती है:
bucket_index = (element - minimum)/span
बकेट इंडेक्स गणना:
-
a) 11बकेट_इंडेक्स = (तत्व – न्यूनतम)/स्पैन
=(11-1)/4
=2
इस प्रकार, तत्व 11 को बकेट[2] में संग्रहीत किया जाएगा।
-
बी) 9
bucket_index = (तत्व – न्यूनतम)/स्पैन
=(9-1)/4
=2
नोट: चूँकि 9 बकेट[1] के लिए एक सीमा तत्व है, इसलिए इसे पिछले तत्व की उसी बकेट में जोड़ने के बजाय बकेट[1] में जोड़ना होगा।
प्रत्येक तत्व के लिए ऑपरेशन करने के बाद, बकेट निम्नानुसार होगी:
चरण 5) अब, प्रत्येक बकेट को इन्सर्टेशन सॉर्ट का उपयोग करके सॉर्ट किया जाएगा। सॉर्टिंग के बाद बकेट-
चरण 6) अंतिम चरण में, बाल्टियाँ एक एकल सरणी में संयोजित की जाएँगी। सरणी इनपुट का क्रमबद्ध परिणाम होगा.
सी/ में बकेट सॉर्ट प्रोग्रामC++
इनपुट:
#include<bits/stdc++.h>
using namespace std;
void bucketSort(vector < double > & input, int No_Of_Buckets)
{
double max_value = * max_element(input.begin(), input.end());
double min_value = * min_element(input.begin(), input.end());
double span = (max_value - min_value) / No_Of_Buckets;
vector<vector <double>>
output;
for (int i = 0; i < No_Of_Buckets; i++)
output.push_back(vector <double>
());
for (int i = 0; i < input.size(); i++)
{
double difference = (input[i] - min_value) / span
-
int((input[i] - min_value) / span);
if (difference == 0 && input[i] != min_value)
output[int((input[i] - min_value) / span) - 1]
.push_back(input[i]);
else
output[int((input[i] - min_value) / span)].push_back(
input[i]);
}
for (int i = 0; i < output.size(); i++)
{
if (!output[i].empty())
sort(output[i].begin(), output[i].end());
}
int index = 0;
for (vector <double> & bucket: output)
{
if (!bucket.empty())
{
for (double i: bucket)
{
input[index] = i;
index++;
}
}
}
}
int main()
{
vector <double>
input ={11,9,21,8,17,19,13,1,24,12
};
int No_Of_Buckets = 5;
bucketSort(input, No_Of_Buckets);
cout<<
"Sorted Output:";
for (int i; i < input.size(); i++)
cout <<input[i]<<" ";
return 0;
}
आउटपुट:
Sorted Output:1 8 9 11 12 13 17 19 21 24
बकेट सॉर्ट कार्यक्रम Python
इनपुट:
def bucketSort(input, No_Of_Buckets):
max_element = max(input)
min_element = min(input)
span = (max_element - min_element) / No_Of_Buckets
output = []
for bucket in range(No_Of_Buckets):
output.append([])
for element in range(len(input)):
diff = (input[element] - min_element) / span - int(
(input[element] - min_element) / span
)
if diff == 0 and input[element] != min_element:
output[int((input[element] - min_element) / span) - 1].append(
input[element]
)
else:
output[int((input[element] - min_element) / span)].append(input[element])
for bucket in range(len(output)):
if len(output[bucket]) != 0:
output[bucket].sort()
index = 0
for bucket in output:
if bucket:
for element in bucket:
input[index] = element
index = index + 1
input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12]
No_Of_Buckets = 5
bucketSort(input, No_Of_Buckets)
print("Sorted Output:\n", input)
आउटपुट:
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
बकेट सॉर्ट इन Java
इनपुट:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void bucketSort(List < Double > input, int No_Of_Buckets) {
double max_value = Collections.max(input);
double min_value = Collections.min(input);
double span =(max_value - min_value) / No_Of_Buckets;
List <
List <
Double > >
output = new ArrayList < >
();
for (int i = 0; i < No_Of_Buckets; i++) {
output.add(new ArrayList < >
());
}
for (Double value: input) {
double difference = (value - min_value) / span - ((value - min_value) / span);
if (difference == 0 && value != min_value) {
output.get((int)((value - min_value) / span) - 1).add(value);
} else {
output.get((int)((value - min_value) / span)).add(value);
}
}
for (List <Double> bucket: output) {
if (!bucket.isEmpty()) {
Collections.sort(bucket);
}
}
int index = 0;
for (List <Double> bucket: output) {
if (!bucket.isEmpty()) {
for (Double value: bucket) {
input.set(index,value);
index++;
}
}
}
}
public static void main(String[] args) {
List <Double>
input = new ArrayList <>
();
input.add(11.0);
input.add(9.0);
input.add(21.0);
input.add(8.0);
input.add(17.0);
input.add(19.0);
input.add(13.0);
input.add(1.0);
input.add(24.0);
input.add(12.0);
int No_Of_Buckets = 5;
bucketSort(input, No_Of_Buckets);
System.out.println("Sorted Output:");
for (Double value: input) {
System.out.print(value + " ");
}
}
}
आउटपुट:
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
पक्ष - विपक्ष
| फ़ायदे | नुकसान |
|---|---|
| तेजी से गणना करें | अन्य एल्गोरिदम की तुलना में अधिक स्थान लेता है |
| इसका उपयोग बाह्य छँटाई विधि के रूप में किया जा सकता है | जब डेटा समान रूप से वितरित नहीं होता है तो खराब प्रदर्शन होता है |
| बाल्टियों को स्वतंत्र रूप से संसाधित किया जा सकता है |
बकेट सॉर्ट जटिलता विश्लेषण
बकेट सॉर्ट की समय जटिलता
- सर्वोत्तम स्थिति जटिलता:यदि सभी ऐरे तत्व समान रूप से वितरित हैं और पहले से सॉर्ट किए गए हैं, तो तत्वों को संबंधित बकेट में बिखेरने के लिए O(n) समय की आवश्यकता होगी। फिर प्रत्येक बकेट को सॉर्ट करने के लिए सम्मिलन सॉर्ट लागत O(k) होगी। इस प्रकार कुल जटिलता O(n+k) होगी।
- औसत मामला जटिलता:औसत मामलों के लिए, हम मानते हैं कि इनपुट समान रूप से वितरित हैं। इस प्रकार बकेट सॉर्टिंग एल्गोरिदम O(n+k) की रैखिक समय जटिलता प्राप्त करता है। यहाँ तत्वों को बिखरने के लिए O(n) समय की आवश्यकता होती है और इन्सर्टेशन सॉर्ट का उपयोग करके उन तत्वों को सॉर्ट करने के लिए O(k) समय की आवश्यकता होती है।
- सबसे खराब स्थिति जटिलता:सबसे खराब स्थिति में, तत्व एक या दो विशिष्ट बाल्टियों में समान रूप से वितरित और केंद्रित नहीं होंगे। उस स्थिति में, बकेट सॉर्ट एक के रूप में काम करेगा बुलबुला सॉर्ट एल्गोरिथ्म. इसलिए, सबसे खराब स्थिति में, बकेट सॉर्ट की समय जटिलता O(n^2) होगी।
बकेट सॉर्ट की स्थान जटिलता
बकेट सॉर्ट की स्पेस जटिलता O(n*k) है। यहाँ n तत्वों की संख्या है और k आवश्यक बकेट की संख्या है।
