Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
BucketSort Implementierung??
Hey Leute,
ich bereite mich gerade auf AuD vor und hab ein Problem mit dem BucketSort.
Könnt ihr mir vlt. erklären, was die rot markierte Zeile macht?
In dieser Zeile fühle ich mein Bucket.
aber ich versteh den ausdruck
buckets[numbers[i]]++;
net? was macht das ++, zählt das mein Indizes in meinen Bucketarray hoch?
Der Code funktioniert und liefet mir einen sortieren Array zurück…
Dank für eure Hilfe!
grüße
import java.util.*;
public class Bucket {
public static int findMaximum(int[] numbers) {
int max = 0;
for (int i = 0; i < numbers.length; i++) {
if (max < numbers[i]) {
max = numbers[i];
}
}
return max;
}
public static int[] sort(int[] numbers) {
int[] buckets = new int[findMaximum(numbers) + 1];
int tmp;
for (int i = 0; i < buckets.length; i++) {
buckets[i] = 0;
}
for (int i = 0; i < numbers.length; i++) {
buckets[numbers[i]]++;
}
int outPos = 0;
for (int i = 0; i < buckets.length; i++) {
for (int j = 0; j < buckets[i]; j++) {
numbers[outPos++] = i;
}
}
return numbers;
}
public static void main(String[] args) {
int[] data = { 5, 3, 0, 2, };
System.out.println("Before: " + Arrays.toString(data));
sort(data);
System.out.println("After: " + Arrays.toString(data));
}
}
[m]buckets[numbers[i]]++;[/m] erhöht den Wert, der in [m]buckets[numbers[i]][/m] steht ganz einfach um eins, macht also das gleiche wie [m]buckets[numbers[i]] = buckets[numbers[i]] + 1;[/m]. Also eigentlich das gleiche, wie [m]i++;[/m], nur dass deine “Variable” etwas komplexer ist.
Beim Bucket Sort hat man zunächst ein Feld von positiven ganzen Zahlen. Wir erstellen dabei weiterhin ein Feld, das alle ganzen Zahlen von 0 bis zur maximalen Zahl im Feld beinhaltet. Anschließend schauen wir, welche Zahlen eingetragen sind und wie oft welche Zahl eingetragen ist.
Die Zeile [m]buckets[numbers[i]]++;[/m] erhöht zunächst einfach den Wert derjenigen Zahl um 1, die an der i-ten Stelle in numbers gespeichert ist. Für den Spezialfall von Feldern ohne sich wiederholende Elemente können wir im Prinzip genauso gut auch den Wert auf eine Konstante setzen, die ungleich 0 ist. Unter der Annahme, dass sich die Zahlen im Feld nicht wiederholen, hat man den folgenden Algorithmus:
1. public static int[] sort(int[] numbers) {
2. int[] buckets = new int[findMaximum(numbers) + 1];
3. for (int i = 0; i < numbers.length; i++) {
4. buckets[numbers[i]] = 1; // diese Zeile gilt nur im Spezialfall
5. }
6. int outPos = 0;
7. for (int i = 0; i < buckets.length; i++) {
8. if (buckets[i] != 0) { // diese Zeile gilt nur im Spezialfall
9. numbers[outPos++] = i;
10. }
11. }
12. return numbers;
13. }
Wenn wir aber auch Arrays mit sich wiederholenden Zahlen miteinbeziehen, müssen wir sicherstellen, dass die Einträge auch an richtiger Stelle im alten Feld wieder eingefügt werden. Hier reicht es nicht mehr, nur eine if-Abfrage zu machen, sondern wir brauchen eine for-Schleife, damit die Zahlen auch an der richtigen Stelle outPos eingefügt werden. Und deswegen steht im [m]buckets[i][/m] die Zahl, die sagt, wie oft ein Element mit dem Wert i im übergebenen Array numbers auftritt. Der Code wird dann zu:
1. public static int[] sort(int[] numbers) {
2. int[] buckets = new int[findMaximum(numbers) + 1];
3. for (int i = 0; i < numbers.length; i++) {
4. buckets[numbers[i]]++;
5. }
6. int outPos = 0;
7. for (int i = 0; i < buckets.length; i++) {
8. for (int j = 0; j < buckets[i]; j++) {
9. numbers[outPos++] = i;
10. }
11. }
12. return numbers;
13. }
Danke!
Aber woher weiß ich den Wert des Bucket?
Angenommen mein array-numbers ist (5,3,0,2)
or (int i = 0; i < numbers.length; i++) {
buckets[numbers[i]] = buckets[numbers[i]] + 1;Wenn ich den Code betrachte, sieht das bei mir so aus:
buckets[numbers[0]] = buckets[numbers[0]] + 1;
daraus folgt für mich:
buckets[5] = buckets[5] + 1;
hat mein bucket dann den wert 5 und wird an die 6. stelle (Ind. 5) im bucketarray geschrieben? meine bucketarray hat die Indizes 0 bis 5…
DANKE DANKE!
vlt. seh ich auch gerade aufn schlauch!!
Der Wert eines Buckets gibt an, wie oft der Bucketindex im zu sortierenden Array vorkommt. Soll heißen, in [m]buckets[5][/m] steht am Ende, wie oft die Zahl 5 im zu sortierenden Array vorkommt.
Zu Beginn ist dieser Wert in allen Buckets 0.
[m]buckets[5]++[/m] erhöht diesen Wert um eins, egal was vorher drinstand.
In deinem Beispiel würde
for( int i = 0; i < numbers.length; i++) {
buckets[numbers[i]]++;
}zuerst [m]buckets[5][/m] um 1 erhöhen, dann [m]buckets[3][/m], [m]buckets[0][/m] und [m]buckets[2][/m].
Danach kannst du, wie Chayyam erklärt hat, über dein buckets-Array laufen und jede Zahl so oft zum Output hinzufügen wie an der entsprechenenden Stelle in buckets angegeben ist.
perfekt! verstanden! vielen dank! 