Bucket Sort Algorithmus

In diesem Tutorial erfahren Sie, wie die Bucket-Sortierung funktioniert. Außerdem finden Sie Arbeitsbeispiele für die Bucket-Sortierung in C, C ++, Java und Python.

Bucket Sort ist eine Sortiertechnik, bei der die Elemente sortiert werden, indem die Elemente zunächst in mehrere Gruppen unterteilt werden, die als Buckets bezeichnet werden . Die Elemente in jedem Bucket werden unter Verwendung eines der geeigneten Sortieralgorithmen sortiert oder es wird rekursiv derselbe Algorithmus aufgerufen.

Es werden mehrere Eimer erstellt. Jeder Eimer ist mit einem bestimmten Bereich von Elementen gefüllt. Die Elemente im Bucket werden mit einem anderen Algorithmus sortiert. Schließlich werden die Elemente des Buckets gesammelt, um das sortierte Array zu erhalten.

Der Prozess der Eimersortierung kann als Streusammelansatz verstanden werden . Die Elemente werden zuerst in Eimer gestreut, dann werden die Elemente von Eimern sortiert. Schließlich werden die Elemente der Reihe nach gesammelt.

Arbeiten der Eimersortierung

Wie funktioniert die Eimersortierung?

Angenommen, das Eingabearray lautet: Eingabearray
Erstellen Sie ein Array der Größe 10. Jeder Steckplatz dieses Arrays wird als Bucket zum Speichern von Elementen verwendet. Array, in dem jede Position ein Eimer ist
Fügen Sie Elemente aus dem Array in die Buckets ein. Die Elemente werden entsprechend der Reichweite des Eimers eingefügt.
In unserem Beispielcode haben wir Buckets mit einem Bereich von 0 bis 1, 1 bis 2, 2 bis 3,… (n-1) bis n.
Angenommen, ein Eingabeelement .23wird verwendet. Es wird mit size = 10(dh .23*10=2.3) multipliziert . Dann wird es in eine ganze Zahl (dh 2.3≈2) umgewandelt. Schließlich wird .23 in Bucket-2 eingefügt . Elemente aus dem Array in die Buckets
einfügen In ähnlicher Weise wird auch .25 in denselben Bucket eingefügt. Jedes Mal wird der Grundwert der Gleitkommazahl genommen.
Wenn wir Ganzzahlen als Eingabe verwenden, müssen wir diese durch das Intervall (hier 10) teilen, um den Bodenwert zu erhalten.
In ähnlicher Weise werden andere Elemente in ihre jeweiligen Eimer eingefügt. Fügen Sie alle Elemente aus dem Array in die Buckets ein
Die Elemente jedes Buckets werden unter Verwendung eines der stabilen Sortieralgorithmen sortiert. Hier haben wir Quicksort (eingebaute Funktion) verwendet. Sortieren Sie die Elemente in jedem Bucket
Die Elemente aus jedem Eimer werden gesammelt.
Dazu wird der Bucket durchlaufen und in jedem Zyklus ein einzelnes Element in das ursprüngliche Array eingefügt. Das Element aus dem Bucket wird gelöscht, sobald es in das ursprüngliche Array kopiert wurde. Sammeln Sie Elemente aus jedem Eimer

Bucket Sort Algorithmus

 BucketSort () erstellt N Buckets, von denen jeder einen Wertebereich für alle Buckets enthalten kann. Initialisieren Sie jeden Bucket mit 0 Werten für alle Buckets. Fügen Sie Elemente in Buckets ein, die dem Bereich für alle Buckets-Sortierelemente in jedem Bucket entsprechen. Sammeln Sie Elemente aus jedem Bucket Ende BucketSort

Beispiele für Python, Java und 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); )

Komplexität

Worst-Case-Komplexität: Wenn sich Elemente im Nahbereich im Array befinden, werden sie wahrscheinlich im selben Bucket platziert. Dies kann dazu führen, dass einige Buckets mehr Elemente aufweisen als andere. Dadurch hängt die Komplexität von dem Sortieralgorithmus ab, der zum Sortieren der Elemente des Buckets verwendet wird. Die Komplexität wird noch schlimmer, wenn die Elemente in umgekehrter Reihenfolge sind. Wenn die Einfügesortierung zum Sortieren von Elementen des Buckets verwendet wird, wird die Zeitkomplexität .O(n²)

O(n²)
Best-Case-Komplexität: O(n+k)
Sie tritt auf, wenn die Elemente gleichmäßig in den Buckets verteilt sind und in jedem Bucket nahezu die gleiche Anzahl von Elementen vorhanden ist.
Die Komplexität wird noch besser, wenn die Elemente in den Eimern bereits sortiert sind.
Wenn die Einfügesortierung zum Sortieren von Elementen eines Buckets verwendet wird, ist die Gesamtkomplexität im besten Fall linear, d. H. O(n+k). O(n)ist die Komplexität zum Herstellen der Buckets und O(k)ist die Komplexität zum Sortieren der Elemente des Buckets unter Verwendung von Algorithmen mit linearer zeitlicher Komplexität im besten Fall.
Durchschnittliche Fallkomplexität: O(n)
Sie tritt auf, wenn die Elemente zufällig im Array verteilt sind. Selbst wenn die Elemente nicht gleichmäßig verteilt sind, wird die Bucket-Sortierung in linearer Zeit ausgeführt. Dies gilt so lange, bis die Summe der Quadrate der Schaufelgrößen in der Gesamtzahl der Elemente linear ist.