Twitter-Code

Meine neueste Rubrik: Twitter-Code. Hier poste ich immer mal wieder Codeschnipsel, die maximal 140 Zeichen lang sind. Außerdem werde ich immer ein bisschen dazu schreiben, wie ich vorgegangen bin und erklären, wie der Code letztendlich dann funktioniert.
Welche Sprachen benutzt du dafür?
Im Moment ist alles reiner C-Code, eventuell kommen später aber auch weitere Sprachen dazu. Der Code selbst ist sicherlich nicht die effizienteste Art und Weise, die Algorithmen zu implementieren, und auch die ausführbaren Dateien am Ende werden nicht besonders klein, also ist es auch nichts für Mikrocontroller oder ähnliches.
Warum machst du das dann?
Weil ich es kann. Es macht mir einfach Spaß, Sachen in C so auszunutzen, dass ich mit möglichst wenig Zeichen das erreiche, was ich erreichen will. Dabei benutze ich natürlich sehr viele Seiteneffekte, die dazu führen, dass der Code ziemlich unlesbar wird und nicht immer wirklich das tut, was man auf den ersten Blick erwarten würde.
Unter welcher Lizenz steht der Code?
Der Code ist lizenziert unter einer Creative Commons Namensnennung 4.0 International Lizenz.
Auch wenn ich nicht glaube, dass irgendjemand das ernsthaft machen möchte, steht es damit jedem frei, den Code in seinen Projekten zu benutzen. Allerdings rate ich stark davon ab. Die Kompaktheit erschwert das debuggen enorm, verringert die Les- und damit auch die Wartbarkeit des Codes und performancetechnisch ist der Code ebenfalls nicht optimal.
Wer allerdings selber ein wenig rumexperimentiert und es schafft, den Code sogar noch kürzer zu machen, der kann mir den Code zukommen lassen, und wenn das gewünscht ist, werde ich ihn (natürlich mit Namensnennung) auch hier auf der Seite veröffentlichen.

Bucketsort

void b(int*a,int n){int b[101]={0};while(!*b&&n&&++b[a[--n]+1]||n<100&&(b[n+1]--&&(a[++*b-1]=n)||++n));}

104 Zeichen

Schritt 1

void b(int*a,int n){
Die Funktion nimmt ein Integer-Array mit Zahlen zwischen 0 und 100 und die Größe des Arrays entgegen.

Schritt 2

int b[101]={0};
Das Array b übernimmt die Funktion der Buckets, allerdings nur von Position 1 bis 101. Die nullte Stelle übernimmt später eine Sonderfunktion. Das Array wird mit 0 initialisiert.

Schritt 3

while(
Die Schleife des Algorithmus. Wer sich Bucketsort mal angeguckt hat, weiß, dass eigentlich drei Schleifen nötig sind. Durch die ganzen Zusammenfassungen konnte ich allerdings alles in eine Schleife packen.

Schritt 4

!*b&&n&&++b[a[--n]+1]
Hier kommt die Besonderheit von b ins Spiel. Solange b an der 0. Stelle 0 (also falsch) ist, wird dieser Teil des Codes überprüft. Im nächsten Schritt wird überprüft, ob n ungleich 0 ist. Ist dies auch der Fall, dann wird Folgendes ausgeführt:
++b[a[--n]+1]
Okay, das ist erstmal ziemlich unübersichtlich. Aber wenn man das Ganze mal übersichtlich aufschreibt, kommt dabei Folgendes raus:
n--;
int t = a[n] + 1;
b[t]++;
Zuerst wird n dekrementiert, also um 1 erniedrigt. Danach wird a an der n. Stelle ausgelesen, darauf wird 1 addiert, und das wird dann benutzt, um b an dieser Stelle zu inkrementieren. Das ist das Prinzip von Bucketsort - es zählt, wie oft jede Zahl in dem Array vorkommt und füllt dann später das Array in dieser Reihenfolge.

Schritt 5

||n<100
Der Trick bei dieser Stelle ist, dass die Überprüfung, ob n < 100 ist, nur ausgeführt wird, wenn der Teil davor falsch ist, weil beide mit einem logischen Oder verknüpft sind. Wenn die erste Bedingung des Oders bereits erfüllt ist, wird die zweite gar nicht überprüft. Im Grunde kann man sich damit sehr leicht eine Art if-else aufbauen. Das erste Mal wird diese Stelle ausgeführt, wenn n 0 ist, denn dann sind alle Werte in die Buckets verteilt und das Array ist komplett durchgegangen.

Schritt 6

&&(b[n+1]--
An dieser Stelle wird wird der Bucket an der n+1. Stelle dekrementiert. Wenn der Wert des Buckets 0 war, dann ist er jetzt -1. Da der Dekrement-Operator allerdings postfix notiert ist, also hinter b steht, wird der Wert 0 zurückgegeben. Da das falsch ist, wird der nächste Teil gar nicht erst ausgeführt, und es wird direkt weitergesprungen zum übernächsten Teil. Wenn der Bucket allerdings einen Wert größer oder gleich 1 hatte, dann wird der nächste Teil ausgeführt.
&&(a[++*b-1]=n)
Da wir den Bucket an der n+1. Stelle betrachten, speichern wir nun n in a, und zwar an der Stelle ++*b-1. Hier wird die nullte Stelle von b benutzt, und zwar als Zähler, wie viele Zahlen schon sortiert im Array stehen. Deswegen wird am Anfang auch abgefragt, ob die nullte Stelle von b 0 ist, denn wenn das nicht der Fall ist, befinden wir uns schon im letzten Schritt. Das wird nötig, weil n erneut als Zählvariable benutzt wird, wir diesmal aber hochzählen. Wenn diese Überprüfung nicht am Anfang stünde, würden wir ewig zwischen den beiden Codeteilen hin- und heroszillieren und die Schleife würde niemals abbrechen. Außerdem würden wir die nullte Stelle immer wieder in die Buckets schreiben.
Die -1 ist nötig, weil wir am Anfang alle Zahlen um 1 hochshiften, um auch die 0 speichern zu können.

Schritt 7

||++n)
Wenn wir mit dem aktuellen Bucket fertig sind, dann kann n erhöht werden, um den nächsten Bucket zu überprüfen. Dieser Teil wird wegen des Oders nur ausgeführt, wenn der Bucket 0 ist und die Überprüfung in Schritt 6 daher falsch.

Schritt 7

);}
Im Schleifenrumpf steht ein leeres Statement, denn hier wird nichts ausgeführt. Abschließend wird die Funktion beendet. Wir brauchen keine Rückgabe, da wir direkt das übergebene Array manipulieren.

Einschränkungen:

Die Funktion bekommt ein int-Array mit den zu sortierenden Werten (a) und die Größe des Arrays (n). Allerdings müssen die Werte zwischen 0 und 100 liegen. Das liegt daran, dass die Speicherallokierung statisch ist, und der Speicherbedarf bei Bucketsort linear wächst. Ich habe das Limit einfach auf 100 gesetzt; natürlich kann man es auch höher setzten, aber es ging mir ja darum, das grobe Prinzip zu implementieren, nicht darum, dass man den Code später wirklich benutzt.