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):
Ein Mensch sortiert eine Menge von Objekten oft derart, dass er zuerst das kleinste Element aus der Menge heraussucht, danach das zweitkleinste, dann das drittkleinste und so weiter, bis er alle Elemente der Reihenfolge nach sortiert hat. Selectionsort folgt genau diesem Schema (wie auch gut im Video zu erkennen): das zu sortierende Feld wird von links nach rechts durchlaufen, wobei das kleinste Element herausgesucht wird; dieses wird im Anschluss ganz nach links sortiert; danach wird ab der zweiten Stelle im Feld nach dem zweitkleinsten Element gesucht und so weiter. Wenn wir das ganze als Code aufschreiben, erhalten wir folgenden Algorithmus:
(1) Selectionsort: a ∈ Nn → Nn:
(2) min ∈ N
(3) for i from 0 to n-1:
(4) min ← i
(5) for j from i+1 to n-1:
(6) if a[j] < a[min]:
(7) min ← j
(8) swap( a[i], a[min] )
(9) return a
Zum Codeverständnis am besten noch einmal Video und Code parallel anschauen; aber Achtung: der Tanz unterscheidet sich in einem kleinen Detail vom hier notierten Algorithmus (wer den Unterschied findet, kann ihn gerne in den Kommentaren erläutern).
Damit haben wir zwei der grundlegendsten Sortieralgorithmen kennengelernt. Sie sind nicht aufregend und nicht sonderlich effizient, aber aufgrund ihrer Einfachheit beliebte Kandidaten zur Erklärung von Programmierkonzepten. In zukünftigen Artikeln wird der Schwierigkeitsgrad aber etwas anheben und wir werden etwas komplexere Algorithmen anschauen; im Zuge dieser Artikel werden wir auch Begriffe wie Komplexität, Landau-Notation, stabiles Sortieren und in-place-Algorithmen kennenlernen – man darf also gespannt sein.
Übrigens: im Tanz zum Bubblesort-Algorithmus ist ein kleiner Fehler enthalten; wer ihn findet, gebe doch bitte in den Kommentaren über seine Erkenntnis Bescheid (ich möchte die Profi-Informatiker unter meinen Lesern bitten, sich mit der Auflösung wenigstens ein paar Tage zurückzuhalten, damit auch der “Nachwuchs” eine Chance bekommt).
Und vielleicht noch eine kleine Diskussionsaufgabe für die Kommentare: in welche Themen-Kategorie sollen nach Meinung der Leser die Artikel zum Thema Algorithmen und Datenstrukturen eingeordnet werden – “Technik” oder “Naturwissenschaften”? Oder doch ganz woanders hin?
Kommentare (23)