Algoritme voor bucket sorteren

In deze tutorial leer je hoe bucket sorteren werkt. Ook vindt u werkende voorbeelden van bucket-sortering in C, C ++, Java en Python.

Bucket Sort is een sorteertechniek waarbij de elementen worden gesorteerd door de elementen eerst in verschillende groepen te verdelen, genaamd buckets . De elementen in elke bucket worden gesorteerd met behulp van een van de geschikte sorteeralgoritmen of recursief hetzelfde algoritme aanroepen.

Er worden meerdere emmers gemaakt. Elke emmer is gevuld met een specifieke reeks elementen. De elementen in de bucket worden gesorteerd met behulp van een ander algoritme. Ten slotte worden de elementen van de bucket verzameld om de gesorteerde array te krijgen.

Het proces van bucket-sortering kan worden opgevat als een scatter-collect- benadering. De elementen worden eerst in emmers gestrooid, daarna worden de elementen van emmers gesorteerd. Ten slotte worden de elementen op volgorde verzameld.

Werking van Bucket Sort

Hoe werkt bucket sorteren?

Stel dat de invoerarray is: Invoerarray
Maak een array van grootte 10. Elke sleuf van deze array wordt gebruikt als een bucket voor het opslaan van elementen. Matrix waarin elke positie een emmer is
Voeg elementen in de emmers uit de array in. De elementen worden ingevoegd volgens het bereik van de bak.
In onze voorbeeldcode hebben we buckets met elk bereik van 0 tot 1, 1 tot 2, 2 tot 3,… (n-1) tot n.
Stel dat er een invoerelement .23wordt genomen. Het wordt vermenigvuldigd met size = 10(dwz. .23*10=2.3). Vervolgens wordt het omgezet in een geheel getal (dwz. 2.3≈2). Ten slotte wordt .23 in emmer-2 gestoken . Elementen in de emmers uit de array invoegen
Op dezelfde manier wordt .25 ook in dezelfde emmer ingevoegd. Elke keer wordt de bodemwaarde van het drijvende-kommagetal genomen.
Als we gehele getallen als invoer nemen, moeten we deze delen door het interval (hier 10) om de vloerwaarde te krijgen.
Evenzo worden andere elementen in hun respectievelijke emmers gestoken. Plaats alle elementen in de emmers uit de array
De elementen van elke bucket worden gesorteerd met behulp van een van de stabiele sorteeralgoritmen. Hier hebben we quicksort (ingebouwde functie) gebruikt. Sorteer de elementen in elke bucket
De elementen uit elke emmer worden verzameld.
Het wordt gedaan door door de emmer te itereren en in elke cyclus een afzonderlijk element in de oorspronkelijke array in te voegen. Het element uit de bucket wordt gewist zodra het naar de originele array is gekopieerd. Verzamel elementen uit elke emmer

Algoritme voor bucket sorteren

 bucketSort () maak N emmers die elk een reeks waarden kunnen bevatten voor alle emmers initialiseer elke emmer met 0 waarden voor alle emmers plaats elementen in emmers die overeenkomen met het bereik voor alle emmers sorteer elementen in elke emmer verzamel elementen uit elke emmer eindemmer Sorteren

Python, Java en C / C ++ voorbeelden

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

Complexiteit

Complexiteit in het ergste geval: als de array elementen van korte afstand bevat, worden ze waarschijnlijk in dezelfde bucket geplaatst. Dit kan ertoe leiden dat sommige bakken meer elementen bevatten dan andere. Het maakt de complexiteit afhankelijk van het sorteeralgoritme dat wordt gebruikt om de elementen van de emmer te sorteren. De complexiteit wordt nog erger als de elementen in omgekeerde volgorde staan. Als invoegsortering wordt gebruikt om elementen van de bucket te sorteren, wordt de tijdcomplexiteit .O(n²)

O(n²)
Best Case Complexity: O(n+k)
Het treedt op wanneer de elementen gelijkmatig in de emmers zijn verdeeld met een bijna gelijk aantal elementen in elke emmer.
De complexiteit wordt nog beter als de elementen in de emmers al gesorteerd zijn.
Als invoegsortering wordt gebruikt om elementen van een bucket te sorteren, zal de algehele complexiteit in het beste geval lineair zijn, dwz. O(n+k). O(n)is de complexiteit voor het maken van de emmers en O(k)is de complexiteit voor het sorteren van de elementen van de emmer met behulp van algoritmen die in het beste geval lineaire tijdcomplexiteit hebben.
Gemiddelde casuscomplexiteit: O(n)
treedt op wanneer de elementen willekeurig in de array worden verdeeld. Zelfs als de elementen niet uniform zijn verdeeld, verloopt bucket-sortering in lineaire tijd. Dit geldt totdat de som van de kwadraten van de emmergroottes lineair is in het totale aantal elementen.