Bucket Sort



  • Hallo!

    Kennt irgendjemand den Algorithmus "Bucket Sort" ??

    Ich hab ihn folgendermassen (fuer 80 Zahlen) in c++ implementiert:

    int feld[15] = {12,13,14,1,2,3,9,8,7,34,12,45,78,12,23};
    int bucket[80] = {0};
    
    for (int i = 0; i < 15; ++i) {
        bucket[feld[i]]++;				
    }
    

    Doch hab ich mir nun sagen lassen muessen, dass dies nicht ganz stimmt.
    Die Begruendung war irgendwie damit verbunden, das bucket sort fuer die Verwendung mit Pointern bestimmt ist ....
    Irgendjemand eine Erklaerung fuer mich??



  • Soweit ich das kenne stimmt das schon.



  • das ist ne völlig korrekte implementierung von bucket sort.



  • Hallo miteinander,

    entschuldigt meine Unkenntniss aber eigentlich sortiert doch der angegebene Algorithmus gar nicht, sondern prüft nur auf das vorhandensein bestimmter Elemente und deren Häufigkeit. Oder? 😕

    Wenn hinterher das Array "feld" sortiert sein soll, müsste ich dann nicht noch die im bucket-Array gezählten Elemente zurück in das feld schreiben?

    int feld[15] = {12,13,14,1,2,3,9,8,7,34,12,45,78,12,23};
    int bucket[80] = {0};
    
    for (int i = 0; i < 15; ++i)
        ++bucket[feld[i]];
    
    for (int i = 0, j = 0; j < 80; ++j)
        for (; bucket[j]; --bucket[j], ++i)
            feld[i] = j;
    

    Viele Grüße
    Knecht



  • @Knecht

    Wenn man das "array feld" sortiert haben will, dann muesste man wohl die werte zurueck schreiben. Doch was tust du, wenn ich das array feld auf const setze?

    int const feld[15] = {12,13,14,1,2,3,9,8,7,34,12,45,78,12,23};
    

    "Bucket Sort" hat ja den Vorteil, dass die Indizes des zweiten arrays die sortierung des ersten arrays implizit beinhaltet.



  • Jo der Knecht hat schon Recht (hui, das reimt sich, und was sich reimt ist gut).
    Ist halt quasi nicht vollständig ohne das Zurückschreiben, am Prinzip ist trotzdem nix falsch -- und darum denke ich ging es.


Log in to reply