Mumien, Analphabeten, Diebe.
Du hast's gut, du hast dein Leben noch vor dir.
Donnerstag, 4. März 2010
Bogosock
nnier | 04. März 2010 | Topic In echt
Wenn man das Programmieren lernt, geht es früher oder später um das Sortieren von Elementen. Denn daran lässt sich prima üben, wie man größere Fragestellungen auf einfache Teilprobleme zurückführt, und ein paar grundlegende Programmstrukturen wie z.B. Verzweigungen (wenn - dann) oder Schleifen (so lange, bis) bimst man gleich mit. Stellen wir uns also mal eine Menge von vergleichbaren Elementen vor, z.B. ganze Zahlen, die zufällig gemischt vorliegen und aufsteigend sortiert werden sollen.



Da gibt es einen Sortieralgorithmus namens Bubblesort, der geht so: Fang ganz vorne an, vergleiche das erste Element mit dem zweiten. Ist das erste größer als das zweite, dann vertausche die beiden, andernfalls tue nichts. Dann gehe einen Schritt weiter, vergleiche das zweite mit dem dritten und so fort bis zum Ende der Liste - host mi.

Am Ende dieses ersten Durchgangs haben wir was? Sie da hinten? Jawoll, wir haben das größte Element am Ende der Liste. Nur das ist sicher. Deshalb fangen wir wieder von vorne an. Und Sie ahnen schon, warum der Algorithmus "Bubblesort" heißt: Weil die Elemente darin nach oben steigen wie die Perlen im Sektglas.



Jetzt höre ich die ganz vorlauten unter Ihnen schon quaken: "Ja, aber man kann den Algorithmus noch verbessern, man muss ja gar nicht jedes Mal bis ganz zum Ende laufen, weil nämlich beim zweiten Durchgang ist ja vorher schon klar, dass das letzte Element das größte ist, also braucht man da nur noch bis zum vorletzten zu laufen und dann nur bis zum drittletzten und so weiter."

Ihnen sei gesagt: Erstens haben Sie recht, zweitens sind Leute wie Sie tendenziell unbeliebt, ich spreche da aus leidvoller Erfahrung. Die einen jedenfalls verbessern schon Algorithmen, während die anderen ganz verstockt auf den Tisch starren und irgendwann in vorwurfsvoll-pampigem Ton fragen: "Und wozu brauche ich das? Wozu soll ich überhaupt Zahlen sortieren, und dann noch so umständlich? Ich verstehe das alles nicht."

Es macht dann wenig Vergnügen, solchen Menschen auch noch den Quicksort darzulegen, denn dieser ist weniger anschaulich zu beschreiben und dazu noch rekursiv. Die Rekursion, einerseits ganz zauberhaft, ist andererseits auch ein wenig unheimlich, denn wenn eine Funktion sich selber aufruft, na, das passt nicht so einfach in unser begrenztes, lineares Denken. Aber versuchen wir's, auch wenn mich Ihre verstockten Gesichter nicht gerade zuversichtlich stimmen. Wir haben wieder eine Liste von zufällig gemischten Zahlen. Wir denken uns eine Zahl als Grenzstein aus und zerhacken die ursprüngliche Liste in zwei Teile. Alles, was kleiner als der Grenzstein ist, kommt in die linke Liste, und was größer als der Grenzstein ist, kommt in die rechte Liste. Dann zerhacken wir jede dieser Teillisten wiederum auf die gleiche Weise und immer so weiter. Am Ende ist alles sortiert - ist doch logisch, oder? Und wenn Sie jetzt noch wissen wollen, was mit Elementen ist, die genau so groß sind wie der Grenzstein oder andere Schlaumeierfragen stellen wollen, dann wenden Sie sich an ihn hier vorne, der weiß ja eh alles besser und ich geh erst mal eine rauchen.



Gott - manche Teilnehmer sind echt anstrengend. Ich meine (hat mal jemand Feuer), die dummen sind anstrengend, das macht auch keinen Spaß, da redest du gegen die Wand, aber diese superschlauen, die alles besser wissen und gleich am Anfang mit Ideen ankommen - nee, do. Am besten sind so durchschnittlich bis leicht überdurchschnittlich interessierte und begabte Teilnehmer, man merkt die Fortschritte, aber die lassen einen in Ruhe erklären und stellen nicht permanent diese oberschlauen Fragen. Na, gehen wir wieder rein.

Was man jedenfalls auch gut sortieren kann: Socken. Es bleiben ja stets ein paar einzelne übrig, dagegen lässt sich einfach nichts machen, und alle paar Monate schütte ich die auf einen Haufen. Hier sehen Sie z.B. den Haufen, wie er sich heute darstellte, nachdem ich bereits etwa 35 Paar Socken wiedervereint und ihrer eigentlichen Verwendung zugeführt habe - dies also ist der harte Kern, dies sind die überzeugten Single-Socken:



Eine besondere Herausforderung sind die schwarzen. Denn auch wenn man sagen könnte: Schwarz ist Schwarz - Sie glauben ja nicht, wie viele unterschiedliche Schwarztöne es gibt, und der eine Stoff ist doch ein wenig dünner als der andere, bzw. hat eine andere Struktur, bzw. der Sockenschaft ist etwa 1 cm kürzer! Und wenn Sie dennoch zu der oberflächlichen Auffassung "Sieht eh kein Mensch" neigen, dann lassen Sie sich bitte gesagt sein: Sobald man zwei nicht ganz sicher zusammengehörende Socken zu einem "Paar" zusammenfügt, verhindert man effektiv, dass die jeweiligen tatsächlichen Partner auch nur den Hauch einer Chance haben, jemals wieder zueinander zu finden. Es kann also nicht nur darum gehen, möglichst viele Einzelsocken zu Paaren zusammenzufügen, drum prüfe, wer sich ewig bindt, ob sich nicht noch was Bessres findt, will sagen: Dann sind da halt noch ein paar einzelne, wir haben doch extra diese einen Meter breite Schublade, dann müssen die da eben noch auf die Zusammenführung warten, das mit der Wiedervereinigung dauerte doch auch seine Zeit und ging dann plötzlich ganz schnell.

Irgendwann allerdings ist durchaus zu überlegen, was man mit den hartnäckigen Restanten so anfängt. Ich weiß übrigens nicht, ob es das Wort "Restanten" tatsächlich gibt, ich hörte es erstmals im Jahre 2006 aus dem Munde eines Aquarienbesitzers, aber das führt jetzt zu weit. Man muss allerdings anmerken, dass das Wort irgendwie plausibel klingt, denn auf Französisch heißt "rester" ja nichts anderes als "bleiben", und von daher.

(Finden Sie eigentlich auch, dass es geradezu unverschämt ist, einen Satz mit "und von daher" zu beenden? Daraus spricht doch die pure Denk- und Formulierungsfaulheit.)

Die übriggebliebenen Socken jedenfalls lassen sich prima weiterverarbeiten. Ich zum Beispiel fertige regelmäßig Schlangen daraus. Ja, regelmäßig - einmal 1978 und dann wieder 2010, mithin also alle 32 Jahre ist es soweit, dass ich einzelne Socken heranziehe, um daraus Schlangen zu basteln. Und wohl dem, der über einen so reichlichen Fundus verfügt! Da kann man dann auch mal einen wirklich schönen gestreiften hernehmen, oder diesen braunen da mit den orangegelben Rosen, der nun schon seit Jahren einzeln in der Schublade herumliegt. Und dann braucht man bloß noch etwas Pappe und Klebstoff, nicht wahr, und kann zusammen mit seinen Kindern aus ausrangierten Gegenständen noch etwas wirklich Sinnvolles herstellen, denn so ein paar Schlangen, die kann man immer mal gebrauchen.



P.S.: "Wie - du hast meinen braunen Socken mit den orangegelben Rosen genommen!? Spinnst du!? Das finde ich jetzt total doof von dir! Der andere taucht bestimmt noch auf!!"

P.P.S.: "Hier, Papa, guck mal! Da ist ja doch noch genau so ein geringelter Socken!"

P.P.P.S.: Der schönste Sortieralgorithmus heißt übrigens Bogosort. Er funktioniert folgendermaßen: Wirf einfach alle Elemente durcheinander. Dann schau nach, ob sie sortiert sind. Wenn nicht, wirf sie erneut durcheinander.

Link zu diesem Beitrag (29 Kommentare)  | Kommentieren [?]   





... hier geht's zu den --> älteren Einträgen *
* Ausgereift und gut abgehangen, blättern Sie zurück!

Letzte Kommentare
Kalender
März 2010
Mo
Di
Mi
Do
Fr
Sa
So
 2 
 3 
 7 
 8 
11
13
15
18
20
25
26
28
30
 
 
 
 
 
Archiv
06/24 04/24 03/24 02/24 01/24 12/23 11/23 10/23 06/23 12/22 11/22 06/22 08/21 06/21 04/21 12/20 09/20 06/20 12/19 11/19 06/19 02/19 08/18 06/18 04/18 03/18 02/18 01/18 10/17 06/17 05/17 02/17 01/17 12/16 11/16 10/16 09/16 08/16 07/16 06/16 05/16 04/16 03/16 02/16 01/16 12/15 11/15 10/15 09/15 08/15 07/15 06/15 05/15 04/15 03/15 02/15 01/15 12/14 11/14 10/14 09/14 08/14 07/14 06/14 05/14 04/14 03/14 02/14 01/14 12/13 11/13 10/13 09/13 08/13 07/13 06/13 05/13 04/13 03/13 02/13 01/13 12/12 11/12 10/12 09/12 08/12 07/12 06/12 05/12 04/12 03/12 02/12 01/12 12/11 11/11 10/11 09/11 08/11 07/11 06/11 05/11 04/11 03/11 02/11 01/11 12/10 11/10 10/10 09/10 08/10 07/10 06/10 05/10 04/10 03/10 02/10 01/10 12/09 11/09 10/09 09/09 08/09 07/09 06/09 05/09 04/09 03/09 02/09 01/09 12/08 11/08 10/08 09/08 08/08 07/08 06/08 05/08 04/08
Über
Über
Erstgespräch