Sortieralgorithmen: Bucket sort

in de-stem •  14 days ago 

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]

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  


This post has been voted on by the SteemSTEM curation team and voting trail. It is elligible for support from @curie and @minnowbooster.

If you appreciate the work we are doing, then consider supporting our witness @stem.witness. Additional witness support to the curie witness would be appreciated as well.

For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!

Please consider using the steemstem.io app and/or including @steemstem in the list of beneficiaries of this post. This could yield a stronger support from SteemSTEM.