Der Bucket sort-Algorithmus ist ein Sortierverfahren, welcher in zwei Schritten aufgebaut ist.
Der erste Schritt besteht darin einen Container zu erstellen, der die Größe n hat. Das n wird im Vorfeld festgelegt und würde im Falle von Zahlen n=10 sein, da es 10 Ziffern gibt. Für Buchstaben wäre n=26 wenn man die Umlaute weglässt.

Als nächstes werden die Elemente in den Container/die Buckets nach folgendem Muster eingefügt:
Nehme das Element an der Stelle list[i] und füge es in dem Bucket bucket[list[i] / n] ein.

In dem Code-Beispiel von unten wird die Zahl 52 in dem 5.Bucket eingefügt, da 52 / 10 = 5.2 = 5 ist. Indizes bestehen aus natürlichen Zahlen, daher wird die Nachkommastelle ignoriert.

Wenn alle Elemente aus der Ursprungsliste eingefügt wurden, dann wird jedes Bucket mit einem weiteren Sortieralgorithmus sortiert. Das kann man z.B. mit dem Insertion sort oder dem Merge sort machen. Hat ein Bucket nur ein Element, so muss dieser Bucket natürlich nicht sortiert werden.
Zum Schluss werden alle Buckets von n=1 bis n=10 durchlaufen und alle Elemente nachfolgend in eine Liste eingefügt die nun aufsteigend sortiert ist.

• Bucket sort (c++)

#include <iostream>
#include <algorithm>
#include <vector>

void bucketSort(int list[], int size) { 
    /* create size-amount buckets */
    std::vector<int> bucket[size]; 
     
    /* place elements into different buckets */
    for (unsigned int i=0; i<size; i++)  { 
       int idx = list[i] / size; // bucketindex
       bucket[idx].push_back(list[i]); 
    } 
  
    /* sort all buckets */ 
    for (unsigned int i=0; i<size; i++) {
       sort(bucket[i].begin(), bucket[i].end());
    }
  
    /* collect all elements from the buckets */
    int index = 0; 
    for (unsigned int i = 0; i < size; i++) 
        for (unsigned int j = 0; j < bucket[i].size(); j++) 
          list[index++] = bucket[i][j]; 
} 
  
int main()  {
    const unsigned int SIZE = 10;
    int list[SIZE] = {52,34,81,13,12,61,73,11,31,22};
    bucketSort(list, SIZE); 
  
    for(unsigned int i=0; i<SIZE; i++) {
        std::cout << list[i] << "\n";
    }
    return 0; 
}  

Quelle
http://personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bucketSort.htm [letzter Zugriff: 13.02.2020, 16:43]