Der Mistkäfer Willi möchte Ordnung in seine Mistkugelsammlung bringen. Am liebsten hätte er sie schön der Grösse nach sortiert, die kleinste Kugel links, die grösste rechts. Leider hat Willi keine Ahnung, wie er das anstellen könnte. Er setzt sich auf eine der Mistkugeln und überlegt, aber es fällt ihm keine Lösung ein.

Da wählt er in seinem Frust zufällig zwei Mistkugeln aus, bei denen die Reihenfolge nicht stimmt, und vertauscht die beiden. Willi ist natürlich klar, dass er damit seine Kugelreihe noch lange nicht sortiert hat. In seiner wachsenden Verzweiflung wählt er ein weiteres Kugelpaar, das nicht richtig geordnet ist, und vertauscht auch dieses.

Diesen Vorgang wiederholt er nun laufend. Nach vielen solchen Vertauschungen stutzt Willi plötzlich: Er findet kein einziges „falsches“ Paar mehr! Enttäuscht wendet er sich ab und versinkt wieder ins Grübeln. Nach einer Weile schaut er auf und betrachtet die Reihe seiner Mistkugeln…¹⁾

In unserer welt sind allemöglichen Sachen sortiert: Rechnungen, Adressen, Kleider, Bankbelege, Personen und vieles mehr. Wozu eigentlich?

Logisch: Sortieren erleichtert das Wiederfinden. Ein Telefonbuch, in welchem die Einträge in zufälliger Reihenfolge abgedruckt sind, wäre nahezu nutzlos.

Aufgabe: Beschreibe den Unterschied zwischen einem Inhaltsverzeichnis und dem Index eines Buches bezüglich der Reihenfolge der Einträge.

Das Kriterium, nach dem wir etwas sortieren ist von wesentlicher Bedeutung: Ein nach den Nachnamen sortiertes Telefonbuch ist von großem Nutzen, sortiert man die Einträge nach den Vornamen ist der Nutzen geringer - oder zumindest ein anderer, ebenso wie eine Sortierung nach den Telefonnummern ein vollkommen anderes Verzeichnis zur Folge hat.

Wie man am Beispiel des Telefonbuchs sieht, gibt es auch kombinierte Sortierkriterien: Die Einträge sind in erster Linie nach der Ortschaft sortiert, innerhalb einer Ortschaft nach Name, bei gleichen Namen nach Vorname.

Aufgabe: In welcher Reihenfolge stehen folgende Namen im Telefonbuch?

• Heinrich Vonberg
• Hubert Vogel
• Franziska Völker
• Marian Völkermann
• Uwe Vockler
• Hans-Herrmann Vollenbirker
• Mark von Salis
• Wilhelm Vogel

Um eine Liste nach einem bestimmten Kriterium sortieren zu können, müssen je zwei Elemente gemäss diesem Kriterium mit einander verglichen werden können. Von zwei beliebigen Elementen muss entscheidbar sein, welches das grössere bzw. das kleinere ist. Natürlich gibt es auch den Fall der Gleichheit zweier Elemente.

Diese Vergleichbarkeit ist z.B. bei Zahlen selbstverständlich. Bei Buchstaben ebenfalls, da gilt die alphabetische Ordnung. Der Vergleich zweier Buchstabenfolgen (also Wörter) gemäss alphabetischer Ordnung ist hingegen schon etwas komplizierter.

Um dieses Problem etwas zu entschärfen, werden wir in unseren Überlegungen stets Arrays mit ganzen Zahlen sortieren, da hier die Vergleichbarkeit durch die Operatoren <,>,= eindeutig gegeben ist.

Aufgabe: Welche Probleme ergeben sich, wenn man eine Schulklasse nach

• Haarfarbe
• Geschlecht
• Hobbies

sortieren möchte?

Man kann für jedes Kriterium, nach dem sortiert werden soll (und kann) die Richtung der Sortierung festlegen: Aufsteigend oder Absteigend. Bei Aufsteigender Sortierung befinden sich die nach der Vergleichsmethode kleineren Elemente am Beginn der Liste, bei absteigender Sortierung ist es umgekehrt.

Im folgenden ist ein unsortiertes Array zu sehen. Die Reihenfolge der Elemente ist durch den Index (in eckigen Klammern) festgelegt, der Wert der jeweiligen Array-Variablen durch die Zuweisung:

$zahlen[1]=7
$zahlen[2]=3
$zahlen[3]=15
$zahlen[4]=5
$zahlen[5]=12

Nun die sortierte Variante:

$zahlen[1]=3
$zahlen[2]=5
$zahlen[3]=7
$zahlen[4]=12
$zahlen[5]=15

Die Werte sind nun aufsteigend sortiert, die Reihenfolge noch immer durch den Index gegeben.

Um einzusehen, welche Bedingungen ein Array erfüllen muss, damit es sortiert ist, hilft uns die Geschichte von Willi und seinen Mistkugeln weiter: Nachdem er viele Kugelpaare vertauscht hat, bei denen die linke Kugel grösser war als die rechte, fand er irgendwann kein solches „falsches“ Paar mehr. Natürlich waren zu diesem Zeitpunkt seine Kugeln vollständig sortiert.

Warum funktioniert das eigentlich? Jede Vertauschung bringt eine grössere Kugel ein Stück nach rechts und eine kleinere Kugel ein Stück nach links. Auf diese Weise trägt jede Vertauschung ein kleines Stück zur Sortierung bei. Jede Vertauschung macht also die Sortierung ein bisschen besser. Die Sortierung ist perfekt, wenn es keine falschen Paare mehr gibt.

Ein Array ist also sortiert, wenn es keine zwei Elemente mit falscher Reihenfolge gibt.

Es ist leicht einzusehen, dass auch die folgende Aussage richtig ist: Ein Array ist sortiert, wenn es keine zwei benachbarten Elemente mit falscher Reihenfolge gibt.

Aufgabe:

• Speichere die Datei array_ausgeben.php²⁾ auf deinem Webspace.
• Teste das Programm mit unterschiedlichen Zahlenreihen und beobachte, was es macht
• Bearbeite den Quelltext. Du findest 3 Aufgaben im Quelltext. Beantworte die Fragen schriftlich in der Datei.

Aufgabe:

• Speichere die Datei sortiert_test.php³⁾ auf deinem Webspace.
• Teste das Programm mit unterschiedlichen Zahlenreihen und beobachte, was es macht
• Bearbeite den Quelltext. Du findest 3 Aufgaben im Quelltext. Beantworte die Fragen soweit möglich schriftlich in der Datei.

Weiter zu BubbleSort