Bucket Sort

Kirby.exe

Top Contributor
Also wir sollen Bucket Sort programmieren, was ich bereits erledigt habe. Jedoch möchte der Prof nun gerne zusätzlich eine "abgewandelte" Form des Algorithmus. Er möchte gerne das "k" setzen können. Ich habe etwas gegooglet etc und habe die Vermutung, dass k für die Anzahl an Bits steht welche verglichen werden. Stimmt diese Annahme? :)
 

Kirby.exe

Top Contributor
Ok das confused mich etwas xD Da ich ja Bits vergleiche und ich nur zwei Möglichkeiten habe xD Oder nach welchem Prinzip soll ich dann einsortieren xD
 
K

kneitzel

Gast
Also generell unterteilst Du etwas in k buckets.

Wie diese Unterteilung erfolgt, ist nicht festgelegt.

Nur eben musst Du da etwas festlegen. Nur eben muss es so sein, dass die Buckets an sich dann "sortiert" sind, sonst macht es wenig sinn.

Also wenn Du Zahlen sortieren sollst und die Zahlen haben maximal einen Wert von n und minimal von 1, dann kannst Du das unterteilen in Werte von
1 bis n/k,
n/k +1 bis 2n/k
2n/k +1 bis 3n/k
...
(k-1)n/k +1 bis n

Und dann kannst Du so Elemente in die Buckets packen um dann jedes Bucket für sich zu prüfen.

Wenn die anzahl der Buckets als 2^x dargestellt werden kann, dann kannst Du zur Sortierung einfach die obersten x bits nehmen.
nehmen wir einmal x = 2:
Dann haben wir 2^2 Buckets = 4 Buckets.

Diese 4 Buckets sind 0 (00), 1 (01), 2 (10) und 3 (11) - durch die binäre Darstellung wird es hoffentlich deutlich, wie die Aufteilung erfolgt.

War das etwas hilfreich zum Verständnis?
 
K

kneitzel

Gast
Nur um den Punkt noch einmal zu unterstreichen:

Wichtig ist, dass dies die obersten bits sind, die sich verändern. Also kein modulo!

Man kann die Werte natürlich auch mit modulo unterteilen, aber dann gewinnt man nichts in Sache Sortierung.
Es soll ja gelten, dass alle Werte in Bucket 1 kleiner sind als alle Werte in Bucket 2 und so ... denn am Ende werden die Inhalte nur aneinander gehängt.

(Dazu zur Not auch immer den Link auf Wikipedia ansehen.
 

Kirby.exe

Top Contributor
Kann es sein dass nur einmal in Buckets sortiert wird und dann alles in eine Liste gemerged wird?

Weil dann habe ich es für k = 1 etwas falsch gemacht xD

Java:
private static void rsortOld(List<Integer> numbers, int k) {
        ArrayList<LinkedList<Integer>> buckets = new ArrayList<>();
        int maxShift = 32;
            
        buckets.add(new LinkedList<Integer>()); // Bucket for Bit = 0
        buckets.add(new LinkedList<Integer>()); // Bucket for Bit = 1
        
        for(int shift = 0; shift < maxShift; shift += k) {
            for(int i = 0; i < numbers.size(); i++) {
                if((numbers.get(i) & (1 << shift)) != 0) {
                    buckets.get(1).add(numbers.get(i));
                }else {
                    buckets.get(0).add(numbers.get(i));
                }
            }
            
            numbers.clear();
            
            for(int i = 0; i < buckets.size(); i++) {
                numbers.addAll(buckets.get(i));
                buckets.get(i).clear();
            }
        }
    }
 
K

kneitzel

Gast
Also was bei Dir fehlt ist:
Nach der Aufteilung in buckets musst Du jedes Bucket, das nicht leer ist, sortieren.
Erst nachdem alle buckets sortiert sind, kannst Du die aneinander fügen.
 

Ähnliche Java Themen

Neue Themen


Oben