Αλγόριθμος ταξινόμησης κάδου

Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί η ταξινόμηση κάδου. Επίσης, θα βρείτε λειτουργικά παραδείγματα τύπου κάδου σε C, C ++, Java και Python.

Το Bucket Sort είναι μια τεχνική ταξινόμησης που ταξινομεί τα στοιχεία διαιρώντας πρώτα τα στοιχεία σε διάφορες ομάδες που ονομάζονται κουβάδες . Τα στοιχεία μέσα σε κάθε κάδο ταξινομούνται χρησιμοποιώντας οποιονδήποτε από τους κατάλληλους αλγόριθμους ταξινόμησης ή αναδρομικά καλώντας τον ίδιο αλγόριθμο.

Δημιουργούνται αρκετοί κάδοι. Κάθε κάδος γεμίζει με ένα συγκεκριμένο εύρος στοιχείων. Τα στοιχεία μέσα στον κάδο ταξινομούνται χρησιμοποιώντας οποιονδήποτε άλλο αλγόριθμο. Τέλος, τα στοιχεία του κάδου συγκεντρώνονται για να πάρουν την ταξινομημένη σειρά.

Η διαδικασία της ταξινόμησης κάδου μπορεί να γίνει κατανοητή ως μια προσέγγιση συγκέντρωσης . Τα στοιχεία πρώτα διασκορπίζονται σε κουβάδες και μετά τα στοιχεία ταξινομούνται. Τέλος, τα στοιχεία συγκεντρώνονται με τη σειρά.

Εργασία της ταξινόμησης κάδου

Πώς λειτουργεί η ταξινόμηση κάδου;

Ας υποθέσουμε ότι ο πίνακας εισόδου είναι: Πίνακας εισόδου
Δημιουργήστε έναν πίνακα μεγέθους 10. Κάθε υποδοχή αυτής της συστοιχίας χρησιμοποιείται ως κάδος για την αποθήκευση στοιχείων. Σειρά στην οποία κάθε θέση είναι ένας κάδος
Εισαγάγετε στοιχεία στους κάδους από τον πίνακα. Τα στοιχεία εισάγονται σύμφωνα με το εύρος του κάδου.
Στο παράδειγμα παραδείγματος, έχουμε κουβάδες από 0 έως 1, 1 έως 2, 2 έως 3,… (n-1) έως n.
Ας υποθέσουμε ότι .23έχει ληφθεί ένα στοιχείο εισόδου . Πολλαπλασιάζεται με size = 10(δηλ. .23*10=2.3). Στη συνέχεια, μετατρέπεται σε ακέραιο (δηλ. 2.3≈2). Τέλος, το .23 εισάγεται στον κάδο-2 . Εισαγωγή στοιχείων στους κάδους από τη συστοιχία
Παρομοίως, το .25 εισάγεται επίσης στον ίδιο κάδο. Κάθε φορά, λαμβάνεται η κατώτατη τιμή του αριθμού κινητής υποδιαστολής.
Εάν πάρουμε ακέραιους αριθμούς ως είσοδο, πρέπει να τον διαιρέσουμε με το διάστημα (10 εδώ) για να πάρουμε την κατώτατη τιμή.
Παρομοίως, άλλα στοιχεία εισάγονται στους αντίστοιχους κουβάδες τους. Εισαγάγετε όλα τα στοιχεία στους κάδους από τον πίνακα
Τα στοιχεία κάθε κάδου ταξινομούνται χρησιμοποιώντας οποιονδήποτε από τους σταθερούς αλγόριθμους ταξινόμησης. Εδώ, χρησιμοποιήσαμε τη γρήγορη ταξινόμηση (ενσωματωμένη λειτουργία). Ταξινόμηση των στοιχείων σε κάθε κάδο
Τα στοιχεία από κάθε κάδο συγκεντρώνονται.
Αυτό γίνεται με επαναλήψεις μέσω του κάδου και εισαγωγή ενός μεμονωμένου στοιχείου στον αρχικό πίνακα σε κάθε κύκλο. Το στοιχείο από τον κάδο διαγράφεται μόλις αντιγραφεί στον αρχικό πίνακα. Συγκεντρώστε στοιχεία από κάθε κάδο

Αλγόριθμος ταξινόμησης κάδου

 bucketSort () δημιουργήστε κάδους N, καθένας από τους οποίους μπορεί να κρατήσει ένα εύρος τιμών για όλους τους κάδους, αρχικοποίηση κάθε κάδου με 0 τιμές για όλους τους κάδους, τοποθετήστε στοιχεία σε κάδους που ταιριάζουν με το εύρος για όλα τα στοιχεία ταξινόμησης κάδων σε κάθε κάδο, συλλέξτε στοιχεία από κάθε κάδο τέλος κουβά

Παραδείγματα Python, Java και C / C ++

Python Java C C ++

 # 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)
Εμφανίζεται όταν τα στοιχεία κατανέμονται τυχαία στον πίνακα. Ακόμα κι αν τα στοιχεία δεν κατανέμονται ομοιόμορφα, το είδος κάδου εκτελείται σε γραμμικό χρόνο. Ισχύει έως ότου το άθροισμα των τετραγώνων των μεγεθών κάδου είναι γραμμικό στον συνολικό αριθμό στοιχείων.