Sommer Sitzung 05

Softwaretechnologie: Java (Teil II, Sommersemester), Notizen zu Sitzung 5

Thema	Stichworte	Material ___________________________
Überblick	Sortieren: bisherige elementare und ein schnelles Verfahren	Beispiele und Literatur: Home
Sortieren: elementar	Wiederholung: Insertion sort, Besprechen: selection sort; Laufzeit? – O(n^2); für große Listen nicht praktikabel; heute deshalb ein schnelleres Verfahren	—
Quicksort	—	—
1. Quicksort: konzeptuell	generelle Technik für schnelle Algorithmen? – Divide-and-conquer; wo gehabt? – binäre Suche; wie umgesetzt? – rekursiver Aufruf für Teile; wir nehmen Wert x als pivot, und sortieren alle Werte so, dass kleinere Werte links von x und größere Werte rechts von x sind (divide), dann für den linken und den rechten Teilbereich jeweils das Gleiche (conquer); in-place (combine automatisch); d.h. 1. Divide-Schritt: partitionieren; 2. Conquer-Schritt: rekursiver Aufruf; 3. Combine-Schritt: entfällt; entwickelt 1962 von Hoare	—
2. Quicksort: top-level implementieren	Gesamtlogik (sort), erster Aufruf (sort)	Code, s. Home
3. Quicksort: Invariante	Beim Partitionieren konzeptuell drei Teilbereich in der Liste: Werte <= x; Werte > x; undefinierte Werte; erste zwei Bereiche Anfangs leer (1. Teil d. Invriante: init), Schleife tauscht wenn Wert kleiner x und gewährleistet so Invariante (2. Teil d. Invriante: maintain); am Ende dritter Bereich leer (3. Teil d. Invriante: termination)
4. Quicksort: Beispiel, partition	Für jeden Bereich, d.h. auf jeder Rekursionsebene: Pivot wählen, i, j bis right jeden ansehen, wenn <= swap, sonst nur weiter; so wächst i wenn getauscht wurde, j rückt auf oder wächst; Bsp. Tafel
5. Quicksort: implementieren, partition	Partition (partition), wie Tauschen? – Puffer nötig (swap)	Code, s. Home
6. Quicksort, Laufzeitverhalten: Best, Worst	Wann weniger gute Laufzeit? – Einteilung einseitig; woher kennen wir das? – Entartete binäre Suchbäume; gleiches Prinzip: wenn immer die eine Seite leer ist wird es wie schlimm? – wir laufen immer über die n Elemente, und würden dann jeweils n Elemente tauschen, d.h. n*n, d.h. O(n²); wann passiert das? – wenn Pivot größtes Element ist; was machen wir dann eigentlich? – wir nehmen ein Element und fügen es an der richtigen Stelle ein; das ist? – Selection sort, gleiche Laufzeit; Rekurrenz bei worst case: T(n) = T(n-1) + T(0) + O(n); bester Fall? – prinzipiell halbe-halbe, so steigt der Gewinn wie bei binärer Suche exponentiell, d.h. die Laufzeit ist logarithmisch, denn für jedes der n Elemente brauchen wir nur log n weitere Schritte, d.h. der beste Fall O(n*log n); Rekurrenz bei best case: T(n) <= 2T(n/2) + O(n); beim Einsetzen, z.B. 6 sehen wir: statt Rekusion komplett können wir Schritte auslassen und stattdessen mit 2 multiplizieren	Einsetzen für n=6; Bäume für best und worst case (s. Teilb. unten)
7. Quicksort, Laufzeitverhalten: Typical	Mittlere Laufzeit insertion sort gleiche Klasse wie worst case: O(n²); Quicksort hingegen typische Laufzeit wie best case; in Praxis Split nicht konstant, aber prinzipiell Wechsel aus best case und worst case, d.h. 0 und n, dann (n-1)/2-1 und (n-1)/2 ist gleiche Klasse wie nur (n-1)/2 und (n-1)/2; denn ob n durch schlechten Split oder von vornherein, bleibt O(n), dann guter Split; schlechter Split wird durch guten Split absorbiert
8. Quicksort: randomized	Mittleres Laufzeitverhalten von oben basiert auf welcher Annahme? – alle Permutationen des Input sind gleich wahrscheinlich; praktisch oft anders; wie umgehen? – input mischen; einfacher? – zufälligen Pivot wählen; wie einbauen ohne bisherige Partition-Methode zu verändern? – Zufallswert mit Position tauschen, die als Pivot gewählt wird, alles sonst wie bisher; impl: wie random zwischen left und right in Java – verschieben: left + random(right-left+1)	Code, s. Home
Sortieren: Laufzeiten	Elementare und schnelle Verfahren (selection, insertion, quicksort); zwei Arten: elementare Verfahren mittel O(n²), schnelle Verfahren mittel O(n log n) allgemeine Grenze f. comparison-based, Quicksort typisch gleiche Klasse wie z.B. Merge sort, theoretisch kann er sehr schlecht sein, aber insgesamt in der Randomized-Version meist das schnellste Verfahren	wolframalpha.com: plot n, n log n, n*n from 1 to 20;
Hausaufgabe	Quicksort verändern; Laufzeit und spezielle Testfälle	Sommer-Aufgabe-04