Hallo…
kann mir mal jemand schnell den Alg. BucketSort VERSTÄNDLICH (also nicht wie im Script) erklären???
Vielen Dank!
Um welches Skript gehts eigentlich? Und was verstehst Du daran nicht?
Grundsaetzlich gehts bei BucketSort einfach darum, dass alle Eintraege, die mit 'A' beginnen in ein "Bucket" kommen, die mit 'B' beginnen ins naechste, etc. Die einzelnen Buckets kann man dann weiter sortieren.
wenn die Schlüsselmenge begrenzt bzw. endlich ist, kann man das Verfahren anwenden. Alle Objekte, die den gleichen Schlüssel bekommen (z.B. Anfangsbuchstaben A oder Hashcode 42, wenn es z.B. nur die Codes 1..100 gibt), werden dann "unsortiert" (wonach auch?) in einen Bucket gesteckt.
Wenn man durch ist (in Linearzeit), kann man die Buckets (die man als Listen implementiert hat) einfach zu einer großen Liste verketten (was in Linearzeit zur Schlüsselmenge geht. Diese ist i.A. deutlich kleiner als die Zahl der zu sortierenden Elemente).
Also fertig in Linearzeit. Nur nicht Herrn Valk erzählen, denn er glaubt das einem nicht [img]
http://www.fb18.de/gfx/25.gif[/img] (naja, wenn man vergisst, die beschr. Schlüsselmenge zu erwähnen)
Wenn man mal unter
"bucket sort" + animation
googelt, findet man mehrere Veranschaulichungen, die einen diese Sortieralgorithmen gut verstehen lassen. Das gilt nicht nur für Bucket Sort. [img]
http://www.fb18.de/gfx/23.gif[/img]
Vielleicht hilft Dir meine Implementierung des BucketSort beim Verständnis? [img]
http://www.fb18.de/gfx/25.gif[/img]
void bucketsort(char *a, int l)
{
int n[ 256]={0},j;while(l-->0)n[*a++]++;for(j=255;j>=0;j--)while(n[j]--)*(--a)=j;
}
Fred, Du machst mir Angst… so langsam sieht das ja richtig nach C aus, was Du produzierst.
Fred, Du machst mir Angst… so langsam sieht das ja richtig nach C aus, was Du produzierst.
Naja, ich wollte halt mal schauen, ob man einen Sortieralgorithmus in einer Zeile (80 Zeichen) implementieren kann. Wenn man das Leerzeichen in der Arraydeklaration wegnimmt (hab ich nur für die korrekte Darstellung im Forum hinzufügen müssen), kommts gerade hin.
Geht aber wahrscheinlich noch kürzer, oder? Wollen wir einen Wettbewerb starten? [img]
http://www.fb18.de/gfx/23.gif[/img]
EDIT: Aus while(l–>0) kann man while(l–) machen, spart nochmal zwei Zeichen.
Wollen wir einen Wettbewerb starten? [img]http://www.fb18.de/gfx/23.gif[/img]
Immer gerne. Aber dazu hätte ich gerne erstmal ordentlich spezifiziert, was Bucketsort _genau_ macht, die Semantik aus Deinem Code rauszupfriemeln hab ich gerade keine Lust drauf *g*
Der Grundgedanke ist folgender: Du hast ein ungeordnetes Array a der Länge l. Der Wertebereich der Elemente des Arrays sollte nicht allzu gross sein, in meinem Beispielcode sinds nur chars, also 256 verschiedene Werte. Jetzt muss man zwei Schritte vornehmen:
1. Die Häufigkeit aller 256 verschiedenen Werte im Array festellen.
Dafür benötigt man ein Array n der Länge 256. Beispiel: n[0] = 7 bedeutet, dass die 0 sieben Mal in dem Array vorkam.
2. Das sortierte Array aus dem "Zählarray" n generieren.
Beispiel: n[0] = 7 bedeutet, dass das Array mit sieben Nullen anfangen muss.
BucketSort benötigt also nur O(n) Speicher und Rechenzeit, was es zu einem sehr effektiven Sortieralgorithmus macht - solange der Wertebereich eben klein genug ist.
Also 5 Bytes hab ich schon gespart. <edit>Mist, das ist ein echtes char-Array, kein String, oder? Dann doch nur 3</edit>
Also 5 Bytes hab ich schon gespart. <edit>Mist, das ist ein echtes char-Array, kein String, oder? Dann doch nur 3</edit>
Drei Bytes habe ich mittlerweile auch einsparen können:
int n[256]={0},j=255;while(l--)n[*a++]++;for(;j>=0;j--)while(n[j]--)*(--a)=j;
Ah, die Initialisierung nach vorne ziehen ist gut. Das eine Byte hab ich woanders gespart: Statt dem j>=0 als Schleifenbedingung tuts auch j+1.
*(–a)
Die Klammern sind unnötig.
Statt dem j>=0 als Schleifenbedingung tuts auch j+1.
Genial! Darauf wäre ich nie gekommen. Zusammen mit den unnötigen Klammern sind wir bereits auf 74 Bytes runter:
int n[256]={0},j=255;while(l--)n[*a++]++;for(;j+1;j--)while(n[j]--)*--a=j;
Wenn man j mit 256 initialisiert kann man statt for(;j+1;j--)while(j--)nehmen.
Wenn man j mit 256 initialisiert kann man statt for(;j+1;j--)while(j--)nehmen.
Sehr schön! Mittlerweile sind wir bei 71 Bytes angekommen:
int n[256]={0},j=256;while(l--)n[*a++]++;while(j--)while(n[j]--)*--a=j;
Lass doch mal das '={0}' weg. Das initialisiert bloss das erste byte des Arrays auf 0, und wenn das reicht, dann reicht auch gar kein init ;)
Post mal, ob das das immer noch geht.
Mo
Lass doch mal das '={0}' weg. Das initialisiert bloss das erste byte des Arrays auf 0, und wenn das reicht, dann reicht auch gar kein init ;)
Nein, denn es werden nicht nur die angegebenen Bytes initialisiert, sondern auch der Rest mit 0.
Post mal, ob das das immer noch geht.
Die Anweisung in "0x0040ba89" verweist auf Speicher in "0xff12ff22".
Der Vorgang "written" konnte nicht auf dem Speicher durchgeführt werden.
Mit einem
#define w while
kann man auch auf 59 Bytes kommen, aber zusammen mit dem #define ist es leider insgesamt mehr:
int n[256]={0},j=256;w(l--)n[*a++]++;w(j--)w(n[j]--)*--a=j;
Vielleicht solltest Du w nicht auf while definieren, sondern auf while(, so kannst Du nochmal 2 Bytes sparen.
Das mit der Initialisierung: Dieses neue C ist auch nicht mehr das, was es mal war…
Mo
Vielleicht solltest Du w nicht auf while definieren, sondern auf while(, so kannst Du nochmal 2 Bytes sparen.
Das funktioniert nicht… und dabei hatte ich Dich immer als C-Guru in Erinnerung [img]
http://www.fb18.de/gfx/25.gif[/img]
Aber wie wäre es hiermit, mitterlweile sind wir bei 53 Bytes + #define:
#define w(x) while(x--)
int n[256]={0},j=256;w(l)n[*a++]++;w(j)w(n[j])*--a=j;
Muss j wirklich 256 sein, und nicht 255? Und wenn es 255 sein muss, kann es doch als unsigned char definiert werden, oder? Und dann kannst Du statt 256 doch ~0 schreiben. Spart ein Byte ;)
Mo
Muss j wirklich 256 sein, und nicht 255?
Ja, denn die Schleife
while(j--)
soll ja 256 Mal durchlaufen. Der Ausdruck j– ist vor dem ersten Durchlauf 256 und vor dem 256ten 1. Vor dem 257ten ist er 0 und die Schleife bricht ab. Im Schleifenrumpf durchläuft j allerdings die Werte 255 bis 0 (wegen des – hinter dem j).
Und wenn es 255 sein muss, kann es doch als unsigned char definiert werden, oder? Und dann kannst Du statt 256 doch ~0 schreiben. Spart ein Byte ;)
Möglicherweise, aber "unsigned char" ist ein paar Bytes länger als "int"…
Muss j wirklich 256 sein, und nicht 255?
Ich denke auch, dass es 255 sein muss.
Edit: Jetzt nicht mehr, Fred's Posting hat mich überzeugt [img]
http://www.fb18.de/gfx/23.gif[/img]
Und wenn es 255 sein muss, kann es doch als unsigned char definiert werden, oder? Und dann kannst Du statt 256 doch ~0 schreiben. Spart ein Byte ;)
Mo
Nur leider nimmt das "unsigned char" dafür mehr Platz ein. [img]
http://www.fb18.de/gfx/26.gif[/img]
Mit einem
#define w while
kann man auch auf 59 Bytes kommen
OK, ich kenne sogar ein #define, wenn man das nicht mitzählt,
kommt man auf 1 Byte [img]
http://www.fb18.de/gfx/10.gif[/img]
Muss j wirklich 256 sein, und nicht 255?
Ich denke auch, dass es 255 sein muss.
Ich habs gerade nochmal vorsichtshalber getestet. Folgender Code spuckt die Zahlen 255 bis 0 aus:
w(j) printf("%i,", j);
OK, ich kenne sogar ein #define, wenn man das nicht mitzählt,
kommt man auf 1 Byte
Meine Hoffnung dabei ist ja, dass man das #define in vielen Routinen nutzen kann und daher die Platzkosten geteilt werden und so gegen 0 gehen. Aber natürlich hast Du im Grunde genommen Recht.
Meine Hoffnung dabei ist ja, dass man das #define in vielen Routinen nutzen kann und daher die Platzkosten geteilt werden und so gegen 0 gehen.
LOL, klasse :-))
Ey, nicht lachen! In meinem Programm wird sie schon von zwei Routinen genutzt:
#include <stdio.h>
#define w(x) while(x--)
void bucketsort(unsigned char *a, int l)
{
int n[256]={0},j=256;
[b]w(l)[/b]
n[*a++]++;
[b]w(j)[/b]
[b]w(n[j])[/b]
*--a=j;
}
void print(unsigned char *a, int l)
{
[b]w(l)[/b] printf(", %i", *a++);
printf("_\n");
}
int main()
{
unsigned char a[] = {255, 0, 128, 127, 7, 4, 11, 5, 3, 4, 9, 8, 1, 7, 2};
const int l = 15;
print(a, l);
bucketsort(a, l);
print(a, l);
return 0;
}
