====== Sortieren ======

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...((Diese Geschichte und weitere Ideen der Einführung sind dem [[http://is.gd/vRR2J9|Skript der ETH Zürich]] entnommen))


====== Wozu sortieren wir? ======

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. 

{{.bilder:aufgabe.png  }}
**Aufgabe:** Beschreibe den Unterschied zwischen einem Inhaltsverzeichnis und dem Index eines 
Buches bezüglich der Reihenfolge der Einträge.

====== Sortierkriterien ======

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.

{{.bilder:aufgabe.png  }}
**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   

===== Vergleichbarkeit =====

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.  

{{.bilder:aufgabe.png  }} **Aufgabe:** Welche Probleme ergeben sich, wenn man eine Schulklasse nach  

  * Haarfarbe 
  * Geschlecht 
  * Hobbies 

sortieren möchte? 

===== Sortierrichtung =====

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.

====== Sortierte Arrays ======

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.

===== Wann ist ein Array sortiert? =====

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.** 

{{.bilder:aufgabe.png  }}
**Aufgabe:** 

  * Speichere die Datei {{.:dateien:array_ausgeben.zip|array_ausgeben.php}}((Zip-Datei auspacken!)) 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. 


{{.bilder:aufgabe.png  }}
**Aufgabe:**   

  * Speichere die Datei {{.:dateien:sortiert_test.zip|sortiert_test.php}}((Zip-Datei auspacken!)) 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]]