faecher:informatik:oberstufe:algorithmen:sortieren:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:algorithmen:sortieren:start [20.02.2020 15:01] – sbelfaecher:informatik:oberstufe:algorithmen:sortieren:start [03.03.2024 14:36] (aktuell) – Marco Kuemmel
Zeile 2: Zeile 2:
  
  
- +  * [[.grundsaetzliches:start|Grundsätzliches zum Thema "Sortieren"]] 
-<blockquote>Ein Sortierverfahren ist ein Algorithmus, der dazu dient, ein Tupel (i. A. ein Array) zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten oder die numerische Ordnung von Zahlen. +  * [[.bubblesort:start|Bubblesort]] 
- +  * [[.selectionsort:start|Selectionsort]] 
-Es gibt verschiedene Sortierverfahren, die unterschiedlich effizient arbeiten bzgl. der Zeitkomplexität (Anzahl der nötigen Operationen) sowie der Platzkomplexität (zusätzlich zum Eingabe-Array benötigter weiterer Speicherplatz). Die Komplexität eines Algorithmus wird üblicherweise in der Landau-Notation dargestellt (s. u. Ausdrücke wie O(n*log(n)). Die Zeitkomplexität hängt bei einigen Sortierverfahren von der anfänglichen Anordnung der Werte im Array ab, man unterscheidet dann zwischen Best Case (bester Fall), Average Case (Durchschnittsverhalten) und Worst Case (schlechtester Fall ~ die Werte sind „maximal ungünstig vorgeordnet“). Häufig sind zusätzliche Faktoren zu beachten, die Einfluss auf Zeit- oder Platzkomplexität haben, zum Beispiel langsamer Zugriff auf extern liegende Daten, begrenzte Größe des Arbeitsspeichers oder ähnliches. +  * [[.insertionsort:start|Insertionsort]] 
- +  * [[.mergesort:start|Mergesort]] 
-//Quelle: [[http://de.wikipedia.org/w/index.php?title=Sortierverfahren&oldid=136466609|Wikipedia]],CC-by-sa-3.0//  +  * [[.quicksort:start|Quicksort]] 
-</blockquote> +  * [[.landau_revisited:start|Aufwandsabschätzung revisited]]
- +
-Sortierverfahren werden mit zunehmender Zahl der zu sortierenden Elemente schnell sehr komplex. Aus diesem Grund eignen sich Algorithmen zum Sortieren sehr gut, um über die Effizienz eines Verfahrens nachzudenken - es gibt viel Optimierungspotential. +
- +
-====== 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 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.  +
- +
-<box 90% round #f4ffc3 #e7f5aa #e7f5aa #e7f5aa |**Aufgabe**> +
-{{  .folder_tools.png|}}  +
-Beschreibe den Unterschied zwischen einem Inhaltsverzeichnis und dem Index eines  +
-Buches bezüglich der Reihenfolge der Einträge. +
-</box> +
- +
-====== 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. +
-<box 90% round #f4ffc3 #e7f5aa #e7f5aa #e7f5aa |**Aufgabe**> +
-{{  .:folder_tools.png|}}  +
-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    +
-</box> +
-===== 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.   +
- +
-<box 90% round #f4ffc3 #e7f5aa #e7f5aa #e7f5aa |**Aufgabe**> +
-{{  .:folder_tools.png|}}  +
- +
-Welche Probleme ergeben sich, wenn man eine Schulklasse nach   +
- +
- +
-  * Haarfarbe  +
-  * Geschlecht  +
-  * Hobbies  +
- +
-sortieren möchte?  +
-</box> +
-===== 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.**  +
- +
-<box 90% round #f4ffc3 #e7f5aa #e7f5aa #e7f5aa |**Aufgabe**> +
-{{  .:folder_tools.png|}}  +
- +
- +
-  * Speichere die Datei {{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.  +
-</box> +
- +
-<box 90% round #f4ffc3 #e7f5aa #e7f5aa #e7f5aa |**Aufgabe**> +
-{{  .:folder_tools.png|}}  +
-  +
- +
-  * Speichere die Datei {{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. +
-</box> +
-Weiter zu [[BubbleSort]]+
  • faecher/informatik/oberstufe/algorithmen/sortieren/start.1582210909.txt.gz
  • Zuletzt geändert: 20.02.2020 15:01
  • von sbel