बाल्टी सॉर्ट एल्गोरिथ्म

इस ट्यूटोरियल में, आप सीखेंगे कि बाल्टी सॉर्ट कैसे काम करता है। इसके अलावा, आप सी, सी ++, जावा और पायथन में बाल्टी प्रकार के काम के उदाहरण पाएंगे।

बाल्टी सॉर्ट एक छँटाई तकनीक है जो तत्वों को पहले समूहों में कई समूहों में विभाजित करके तत्वों को क्रमबद्ध करती है जिन्हें बाल्टी कहा जाता है । प्रत्येक बाल्टी के अंदर के तत्वों को किसी भी उपयुक्त छँटाई एल्गोरिदम का उपयोग करके या एक ही एल्गोरिथ्म को पुन: कॉल करके सॉर्ट किया जाता है।

कई बाल्टी बनाई जाती हैं। प्रत्येक बाल्टी तत्वों की एक विशिष्ट श्रेणी से भरी होती है। बाल्टी के अंदर के तत्वों को किसी अन्य एल्गोरिदम का उपयोग करके सॉर्ट किया जाता है। अंत में, सॉर्ट किए गए सरणी को प्राप्त करने के लिए बाल्टी के तत्वों को इकट्ठा किया जाता है।

बाल्टी के प्रकार की प्रक्रिया को एक बिखराव-इकट्ठा दृष्टिकोण के रूप में समझा जा सकता है । तत्वों को पहले बाल्टी में बिखराया जाता है फिर बाल्टी के तत्वों को छांटा जाता है। अंत में, तत्वों को क्रम में इकट्ठा किया जाता है।

बकेट सॉर्ट का कार्य

बाल्टी क्रमबद्ध कैसे काम करती है?

मान लीजिए, इनपुट सरणी है: इनपुट सरणी
आकार का एक सरणी बनाएं 10. इस सरणी के प्रत्येक स्लॉट को भंडारण तत्वों के लिए एक बाल्टी के रूप में उपयोग किया जाता है। सरणी जिसमें प्रत्येक स्थिति एक बाल्टी है
सरणी से बाल्टी में तत्व डालें। तत्वों को बाल्टी की सीमा के अनुसार डाला जाता है।
हमारे उदाहरण कोड में, हमारे पास 0 से 1, 1 से 2, 2 से 3, … (n-1) से लेकर n तक की प्रत्येक बाल्टियाँ हैं।
मान लीजिए, एक इनपुट तत्व .23लिया गया है। यह size = 10(यानी। .23*10=2.3) से गुणा किया जाता है । फिर, इसे पूर्णांक (यानी। 2.3≈2) में बदल दिया जाता है । अंत में .23 को बाल्टी -2 में डाला जाता है । उसी प्रकार से बकेट में तत्वों को डालें।
इसी तरह से .25 को भी उसी बकेट में डाला जाता है। हर बार, फ्लोटिंग पॉइंट नंबर का फ्लोर वैल्यू लिया जाता है।
यदि हम पूर्णांक संख्याओं को इनपुट के रूप में लेते हैं, तो हमें इसे फर्श के मूल्य को प्राप्त करने के लिए अंतराल (10 यहाँ) से विभाजित करना होगा।
इसी तरह, अन्य तत्वों को उनकी संबंधित बाल्टियों में डाला जाता है। सरणी से सभी तत्वों को बाल्टी में डालें
प्रत्येक बाल्टी के तत्वों को किसी भी छंटाई एल्गोरिदम का उपयोग करके सॉर्ट किया जाता है। यहां, हमने क्विकसॉर्ट (इनबिल्ट फंक्शन) का इस्तेमाल किया है। प्रत्येक बाल्टी में तत्वों को क्रमबद्ध करें
प्रत्येक बाल्टी से तत्वों को इकट्ठा किया जाता है।
यह बाल्टी के माध्यम से पुनरावृत्ति और प्रत्येक चक्र में एक व्यक्तिगत तत्व को मूल सरणी में डालने के द्वारा किया जाता है। मूल सरणी में कॉपी करने के बाद बाल्टी से तत्व मिटा दिया जाता है। प्रत्येक बाल्टी से तत्वों को इकट्ठा करें

बाल्टी सॉर्ट एल्गोरिथ्म

 बकेटसर्ट () एन बकेट्स बनाते हैं जिनमें से प्रत्येक में सभी बकेट्स के लिए मानों की एक श्रंखला हो सकती है। प्रत्येक बकेट को 0 बाल्टी के साथ शुरू करें। एंड बाल्टी

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी ++

 # Bucket Sort in Python def bucketSort(array): bucket = () # Create empty buckets for i in range(len(array)): bucket.append(()) # Insert elements into their respective buckets for j in array: index_b = int(10 * j) bucket(index_b).append(j) # Sort the elements of each bucket for i in range(len(array)): bucket(i) = sorted(bucket(i)) # Get the sorted elements k = 0 for i in range(len(array)): for j in range(len(bucket(i))): array(k) = bucket(i)(j) k += 1 return array array = (.42, .32, .33, .52, .37, .47, .51) print("Sorted Array in descending order is") print(bucketSort(array))

 // Bucket sort in Java import java.util.ArrayList; import java.util.Collections; public class BucketSort ( public void bucketSort(float() arr, int n) ( if (n <= 0) return; @SuppressWarnings("unchecked") ArrayList() bucket = new ArrayList(n); // Create empty buckets for (int i = 0; i < n; i++) bucket(i) = new ArrayList(); // Add elements into the buckets for (int i = 0; i < n; i++) ( int bucketIndex = (int) arr(i) * n; bucket(bucketIndex).add(arr(i)); ) // Sort the elements of each bucket for (int i = 0; i < n; i++) ( Collections.sort((bucket(i))); ) // Get the sorted array int index = 0; for (int i = 0; i < n; i++) ( for (int j = 0, size = bucket(i).size(); j < size; j++) ( arr(index++) = bucket(i).get(j); ) ) ) // Driver code public static void main(String() args) ( BucketSort b = new BucketSort(); float() arr = ( (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47, (float) 0.51 ); b.bucketSort(arr, 7); for (float i : arr) System.out.print(i + " "); ) )

 // Bucket sort in C #include #include #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) printf("-------------"); printf("Bucktets after sorting"); for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) void print(int ar()) ( int i; for (i = 0; i data); cur = cur->next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); printf("Initial array: "); print(array); printf("-------------"); BucketSort(array); printf("-------------"); printf("Sorted array: "); print(array); return 0; )

 // Bucket sort in C++ #include #include using namespace std; #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) cout << "-------------" << endl; cout << "Bucktets after sorted" << endl; for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) for (i = 0; i next; free(tmp); ) ) free(buckets); return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) // Print buckets void print(int ar()) ( int i; for (i = 0; i < NARRAY; ++i) ( cout << setw(3) << ar(i); ) cout << endl; ) void printBuckets(struct Node *list) ( struct Node *cur = list; while (cur) ( cout << setw(3)  next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); cout << "Initial array: " << endl; print(array); cout << "-------------" << endl; BucketSort(array); cout << "-------------" << endl; cout << "Sorted array: " << endl; print(array); )

जटिलता

सबसे खराब स्थिति जटिलता: जब सरणी में करीब सीमा के तत्व होते हैं, तो उन्हें उसी बाल्टी में रखे जाने की संभावना होती है। इसके परिणामस्वरूप कुछ बाल्टियाँ दूसरों की तुलना में अधिक संख्या में हो सकती हैं। यह बाल्टी के तत्वों को सॉर्ट करने के लिए उपयोग किए जाने वाले सॉर्टिंग एल्गोरिथ्म पर निर्भर करता है। जब तत्व रिवर्स ऑर्डर में होते हैं तो जटिलता और भी बदतर हो जाती है। यदि प्रविष्टि सॉर्ट का उपयोग बाल्टी के तत्वों को सॉर्ट करने के लिए किया जाता है, तो समय जटिलता बन जाती है ।O(n²)

O(n²)
बेस्ट केस कॉम्प्लेक्सिटी: O(n+k)
यह तब होता है जब प्रत्येक बाल्टी में तत्वों को समान रूप से लगभग समान तत्वों के साथ बाल्टी में वितरित किया जाता है।
यदि पहले से ही बाल्टियों के अंदर के तत्वों को छाँट लिया जाए तो जटिलता और भी बेहतर हो जाती है।
यदि प्रविष्टि सॉर्ट का उपयोग बाल्टी के तत्वों को सॉर्ट करने के लिए किया जाता है तो सबसे अच्छी स्थिति में समग्र जटिलता रैखिक होगी। O(n+k)। O(n)बाल्टी बनाने के O(k)लिए जटिलता है और सबसे अच्छे मामले में रैखिक समय जटिलता वाले एल्गोरिदम का उपयोग करके बाल्टी के तत्वों को छांटने के लिए जटिलता है।
औसत केस जटिलता: O(n)
यह तब होता है जब तत्वों को सरणी में यादृच्छिक रूप से वितरित किया जाता है। भले ही तत्वों को समान रूप से वितरित नहीं किया जाता है, लेकिन बाल्टी प्रकार रैखिक समय में चलता है। यह तब तक सही है जब तक कि बाल्टी के आकार का योग कुल तत्वों की संख्या में रैखिक न हो।