Bucketsort-Frage

[derweise]

Hallo, wir BucketSort mit Listen programmieren. Ich weis nicht so recht, wie ich das machen soll. Meine Überlegung wäre:

1.Ich habe das Array A,mit den unsortieren Zahlen
2. Ich ermittle aus dem Array den Maximalwert
3. LEge ein neues Array B an der Länge des Maximalwertes
4. Für jede Zahl, die in a vorkommt, trage ich an der entsprechenden Indexstellte in B die Zahl ein, wie oft die Zahl vorkommet.
-->Z.b. kommt die Zahl 5 zwei Mal vor, dann steht in B ander Index-Stelle 5 die Zahl 2 drin.
5. Und jetzt erst kommen meine Listen. Ich gehe durch B durch und wenn immer ich eine Zahl größer 0 finde, dann erstelel ich dafür einen "Knoten"(die Liste besteht aus Knoten), den Knoten gebe ich als Paramater mit den Index-Wert und das, was an der Index-Stelle steht. D.h. ich habe so viele Knoten, wie ich unterschiedliche Zahlen habe
6. Bei der ausgabe sage ich dann einfach, dass jeder Knoten seinen Index mal dem anderen Wert ausgibt.

Aber irgendwie kommt der Teil mit den Listen zu spät denke ich, die Sortierung hat ja eigentlich schon stattgefunden? irgendwas ist da falsch.

 

[derweise]

keiner ne idee?

 

[Landei]

Tante Wikipedia hat doch sogar schon fertigen Code für dich: Bucketsort ? Wikipedia

 

[derweise]

ja, aber da spielen listen keine rolle. ich muss listen verwenden

 

[Landei]

Du bist nicht in der Lage, Arrays durch Listen auszutauschen???

(ungetestet)

void bucketsort(int n, int anzahlBuckets, List<Integer> z) {
    // histogramm erstellen
    List<Integer> buckets = new ArrayList<Integer>();
    buckets.addAll(Collections.nCopy(buckets, Integer.valueOf(0));
    for (int i=0; i<n; i++) {
         buckets.set(z.get(i), buckets.get(z.get(i)) + 1);
    }
    // sortieren
    int x=0;
    for (int i=0; i<anzahlBuckets; i++) {
         while (buckets.get(i) > 0) {
                z.set(x,i);
                x++;
                buckets.set(i, buckets.get(i)--);
         }
    }
  }