In den letzten Artikeln habe ich versucht, das grundlegende Vorgehen beim Programmieren darzulegen – einerseits natürlich, um die Idee des Programmierens selbst zu erläutern, andererseits aber natürlich auch, um die Grundlagen für die Erklärung der eigentlichen Aufgabe der Informatik zu schaffen: der Problemlösung. Der durchschnittliche Informatiker hat im Arbeitsalltag nämlich in der Regel relativ wenig mit Computern an sich zu tun (abgesehen davon, dass er an ihnen programmiert); viel öfter ist er damit beschäftigt, für ein gegebenes Problem nach einer Lösung zu suchen. Ein Problem kann hier alles mögliche sein; von der Lösung einer einfachen Gleichung über die Suche nach dem kürzesten Pfad auf einer Landkarte bis hin zu komplexen Simulationen ist alles denkbar. Die Lösung ist natürlich immer vom Problem abhängig, wobei typischerweise für ein Problem viele verschiedene Lösungen mit jeweils ganz eigenen Vor- und Nachteilen existieren. Ein häufig anzutreffendes, bereits vielfach gelöstes und daher teilweise trivialisiertes Problem ist die Sortierung einer Menge von Daten. Was ein Mensch relativ intuitiv machen kann, ist für den Computer harte Arbeit (der Mensch wird dem Computer beim Sortieren trotzdem immer unterlegen bleiben) und wird von den sogenannten Sortieralgorithmen erledigt. Und um zwei deren einfachste Vertreter soll es heute gehen (übrigens werden Sortieralgorithmen üblicherweise auf der Grundlage von Feldern natürlicher oder ganzer Zahlen erklärt und an diese Konvention möchte ich mich hier auch halten).
Thilo drüben im Mathlog hat bereits vor einiger Zeit ein wunderbares Video zum Bubblesort-Algorithmus gepostet. Für alle, die das Video noch einmal sehen wollen oder noch nicht gesehen haben: hier ist es.
Der Algorithmus folgt einem einfachen Schema, bei welchem von links nach rechts durch das zu sortierende Feld durchgehend immer zwei benachbarte Elemente miteinander verglichen werden; ist das linke Element größer als das rechte, so werden beide Elemente ausgetauscht und somit die größeren Elemente nach rechts verschoben. Ist man so einmal durch das Feld durchgewandert, beginnt man von vorne – so lange, bis alle Elemente sortiert sind. Der Algorithmus wird Bubblesort genannt, da die einzelnen Elemente wie Blasen nach oben (im Feld nach rechts) aufsteigen; zuerst landet das größte Element ganz rechts, danach folgt das zweitgrößte Element und so weiter. Dieses paarweise Vergleichen und Vertauschen ist im Video oben gut zu sehen. Übrigens muss nur beim ersten Durchlauf nur bis ganz nach rechts gesucht werden – danach ist garantiert, dass sich das größte Element an dieser Stelle befindet. Nach dem zweiten Durchlauf ist dementsprechend das zweitgrößte Element garantiert an der zweiten Stelle von rechts und so weiter (auch das sieht man im Video gut, wenn sich die “fertigen” Tänzer am Ende eines Durchlaufes umdrehen). Möchte man den Algorithmus in einer Programmiersprache umsetzen, so wird er ungefähr so aussehen (der Code sollte jetzt eigentlich jedem verständlich sein; wichtig: Felder sind hier 0-indiziert, der erste Index ist also “0” und nicht “1”, der größte Index bei einer Feldlänge von “n” demzufolge “n-1” und nicht “n”; mit “swap” wird die Funktion bezeichnet, die 2 Elemente im Feld austauscht):
(1) Bubblesort: a ∈ Nn → Nn:
(2) for i from n-1 to 1:
(3) for j from 1 to i:
(4) if a[j-1] > a[j]:
(5) swap( a[j-1], a[j] )
(6) return a
Wer den Algorithmus jetzt noch nicht ganz verstanden hat, der vergleicht am besten den Code mit obigem Video; dann sollte es (hoffentlich) klar werden. Bubblesort ist ein relativ ineffizienter Sortieralgorithmus, da er relativ viele Vergleiche benötigt, um ein gegebenes Feld zu sortieren; es gibt weitaus effizientere Algorithmen für die Lösung dieses Problems, aber die werde ich ein andermal erläutern.
An dieser Stelle möchte ich einen anderen Sortieralgorithmus vorstellen, den sogenannten Selectionsort-Algorithmus. Der Algorithmus ist ähnlich ineffizient wie Bubblesort, entspricht aber im Vorgehen eher dem intuitiven, “menschlichen” Ansatz – daher hier die Erwähnung. Zur Einstimmung aber erst einmal noch ein Video (bei welchem der Macher des Videos scheinbar ob der Länge des Tanzes die Geduld verloren und nach kurzer Zeit die Fast-Forward-Funktion aktiviert hat):
Kommentare (23)