AD Aufgabe 3 - HackMD

# AD Aufgabe 3 ## A Beste Eingabe für QuickSort 1. Konstruieren Sie für das QuickSort-Verfahren unter der Annahme, dass das Mischen entfällt, für N=3, für die ersten N natürlichen Zahlen eine Eingabe, die im ersten Durchgang der Partitionierung nur 3 Vergleiche benötigt. --- QuickSort Folien ``` function partitio(a, lo, hi): i := lo j := hi+1 pivot := a[lo] while true: while a[++i] < pivot: if i == hi: break while pivot < a[--j]: if j == lo: break if i >= j: break swap a[i] with a[j] swap a[lo] with a[j] return j ``` `a = [3, 2, 1]` 2. Wieviel Vergleichs- und Tauschoperationen werden für die Eingabe unter A.1 benötigt, bis das Array vollständig sortiert ist? --- 6 Vergleichs- und 2 Tauschoperationen 3. Konstruieren Sie für N=3 eine beste Eingabe, die sich bzgl. der Vergleichs- und Tauschoperationen optimal verhält. Gewichten Sie dabei Vergleichs- und Tauschoperationen gleich. Weisen Sie das Verhalten nach. --- `a = [2, 1, 3]` mit 5 Operationen 4. Leiten Sie aus den Erkenntnissen für N=3 eine beste Eingabe für N=7 ab. `a = [4, 2, 1, 3, 6, 5, 7]` mit 22 Operationen Der Pivot sollte bei jeder Patition der Median sein. Und der rest fertig "sortiert" ## B Beweisidee QuickSort Erläutern Sie die Beweisidee zum Nachweis, dass QuickSort leicht überlineares Verhalten mit probabilistischer Garantie zeigt. --- Wir brauchen eine probabilistische Garantie die uns etwas für die größe des größten Teil der Patition sagt. Zum Beispiel das der größten Teil meistens kleiner als 3/4 ist. Wenn wir die Partitionen in einem Baum aufzeichnen, ist der Schritt von einem Elternknoten zu dem größeren Kind 3/4. Also hat ein Elternknoten 4/3 mal so viele Elemente wie das größte Kind. Damit hat der Baum eine maximale Tiefe von log 4/3 N. ## C Optimierungen von QuickSort Nennen Sie die Probleme und die jeweiligen Optimierungen für das QuickSortVerfahren. --- + Wenn das Pivotelement immer das Größte/Kleinste ist, hat QuickSort quadratische Laufzeit. Den Median als Pivotelement wählen + QuickSort ist für kleine Teilabschnitte genauso ineffizient wie MergeSort. Ab einer Grenze ein besseres Verfahren wählen. ## D Heapify für ein Eingabe-Array Erstellen Sie für die Eingabe " A N G E L S P I T Z E " ein Heapgeordnetes Array mit linearem Aufwand. Zeichnen Sie dazu für die ersten 4 Schritte die Graphen und kommentieren Sie die Operationen zur partiellen Herstellung der Heap-Ordnung nachvollziehbar. Zeigen Sie, dass Ihre Lösung linearen Aufwand benötigt. --- wir nutzen ein binary heap -> einfügen > worst: O(log n) und avarage: O(1) 1. root anhängen -> Vergleichsoperationen: 0 ``` a ``` 2. anhängen -> Vergleichsoperationen: 1 ``` a / n ``` 3. anhängen -> Vergleichsoperationen: 1 ``` a / \ n g ``` 4. anhängen und bubble up -> Vergleichsoperationen: 2 ``` a a / \ / \ n g -> e g / / e n ``` 5. finished ``` a / \ / \ / \ / \ e g / \ / \ / \ / \ i e s p / \ / \ n t z l ``` "Zeigen Sie, dass Ihre Lösung linearen Aufwand benötigt" Sie brauch O(n log n) Wir messen den aufwand der Insersions die wir brauchen. Wir wollen alle n Elemente eifügen. Wir müssen sie jemals nur genau 1 mal einfügen. Damit brauchen wir n Insersions. Eine Insertion brauch im best case O(1) aber in schritt 4 brauch sie schon O(2). Damit sind wir über linar. E sagt aber ja schon das wir eine binären Head verwenden sollen. ??? ## E HeapSort für D (Handprotokoll bis zum 4’ten Element) Wenden Sie auf den binären Heap aus D das HeapSort-Verfahren an. Zeichnen Sie für die ersten 4 Schritte die Graphen und kommentieren Sie die Operationen zur Wiederherstellung der Heapordnung nachvollziehbar für jeden Sortierschritt. 1. remove a: swap a with l, remove a, sink l ``` e / \ / \ / \ / \ e g / \ / \ / \ / \ i l s p / \ / n t z ``` 2. remove e: swap e with z, remove e, sink z ``` e / \ / \ / \ / \ i g / \ / \ / \ / \ n l s p / \ z t ``` 3. remove e: swap e with t, remove e, sink t ``` i / \ / \ / \ / \ l g / \ / \ / \ / \ n t s p / z ``` 4. remove l: swap l with z, remove l, sink z ``` l / \ / \ / \ / \ n g / \ / \ / \ / \ z t s p ``` ## F Sortieren von riesigen Datenbeständen Sie haben die Aufgabe eine Datei mit N Datensätzen zu sortieren, die nicht vollständig in den Speicher passen. Der Speicher erlaubt die Bearbeitung von M Datensätzen mal einer Konstante. 1. Skizzieren Sie ein Verfahren, das alle N-Datensätze der Eingabe in eine sortierte Datei überführt. Benennen Sie die Datenstrukturen und/oder Algorithmen, die Sie für die Lösung verwenden. --- External Memory Merge Sort 1. Lese einen M großen Block ein, sortiere ihn komplent, z.B mit QuickSort, und speichere ihn Block wieder zurück. Wiederhole dies bis alles in Blöcken sortiert ist. 2. Merge K Blöcke mit eine K-Wege Merge Dazu wird für jeden Block ein Buffer im Speicher angelegt welcher immer das kleinste Element des Blockes enthält. Wenn ein Buffer leer ist wird er aus dem Speicher aufgefüllt. K im Zusammenhang mit M bestimmt die Größe der Buffer. Das heißt F sollte so gewählt werden das es möglichts wenige IO Zugriffe gibt. Die sortierten Elemente werden auch mit einem Buffer wieder auf die Platte geschrieben. 3. Wieder hole 2. auf den neuen Blöcken aus 2. bis es nur noch ein Block gibt. Dieser ist vollstängig sortiert. ## G Wahl des Sortierverfahrens 1. Ihre Aufgabe ist es das Sortierverfahren für ein Tabellenkalkulationsprogramm auszuwählen. Welche Eigenschaft sollte das Verfahren auf jeden Fall haben? Welche Eigenschaften wären wünschenswert? Für welches Verfahren entscheiden Sie sich? Begründen Sie Ihre Antworten. --- Das Sortierverfahren sollte in jedem Fall korrekt arbeiten, auch sollte es für vergleichsweise kleine Mengen, also bis mindestens 1E6 Elementen, schnell arbeiten. Auch wäre es gut würde es mit großer Häufigkeit gleicher Werte, sowie vorsortierten Eingaben gut zurechtkommen. Wir würden uns für eine Merge-Sort Implementierung entscheiden die bei kleinen Teilmengen auf Insertion-Sort wechselt. Merge-Sort hat mit sortiertem Input kein Problem während dies für Insertion-Sort sogar den best-case darstellt. Auch haben beide kein Problem mit gleichen Werten. Währennd Merge-Sort vergleichweise langsam wird bei kleinen Mengen können wir hier auf Insertion-Sort wechseln, welcher wiederum bei großen Mengen langsam ist. 2. Kundendaten Ihrer Vertragspartner liegen Ihnen teilweise vorsortiert vor. Für welches Sortierverfahren entscheiden Sie sich? Welches Verfahren würden Sie auf jeden Fall ausschließen? Begründen Sie Ihre Antworten. --- Wir würden QuickSort ohne Shuffel auf jeden Fall ausschließen, da es bei vorsortierten Daten eine quadratische Laufzeit aufweist. Merge-Sort dagegen verhält sich bei vorsortiertem Input gut, da dann im Prinzip zwei sortierte Mengen nur aneinander gehängt werden müssen. Falls die Datenmege klein und die vorsortierten Teile groß sind, nutzen wir Insersion-Sort. Falls unser gutgläubiger Vertragspatner allerdings überhaubt keine Ahnung von Computern hat und uns nach Rechenstunden bezahlt, nutzen wir Bogosort. 3. Die Anforderungen an ein Sortierverfahren lauten: 1. Es darf kein zusätzlicher Speicher für das Sortieren benutzt werden. --- Heap-Sort, da es ein In-place Verfahren ist und nur einen konstanten zusätlichen Speicher benötigt. 2. Eine ggf. vorsortierte relative Reihenfolge soll beim Sortieren erhalten bleiben. --- Merge-Sort, da es stabil ist und somit die relative Reihenfolge gleichwertiger Elemente bewahrt. 3. Das Verfahren sollte sich unter den Randbedingungen optimal verhalten. Für welches Verfahren entscheiden Sie sich? Begründen Sie die Antwort. --- Heap-Sort oder Merge-Sort, beide sind im Durchschnitt und im schlechtesten Fall gleich gut (O(n log(Nn))), wobei hier zweiteres wichtig ist. Die Auswahl würde sich anschließend danach richten wie viel Speicher zur Verfügung steht oder ob es wichtig ist die relative Reihenfolge der Elemente zu bewahren. ## H Verbessertes Löschen in BST Das allgemeine Löschen im BST wählt immer das Minimum des rechten Teilbaums. Es wäre allerdings auch denkbar das Maximum des linken Teilbaums zu wählen und dieses an die Stelle des zu löschenden Schlüssels zu setzen. 1. Implementieren Sie eine Methode, die beim Löschen eines beliebigen Schlüssels, das Maximum des linken Teilbaums verwendet. 2. Verbessern Sie dann das Löschen im BST, in dem Sie beim Löschen immer den größeren Teilbaum verwenden, um den Schlüssel zu bestimmen, der das zu löschende Element ersetzt. 3. Zeigen Sie, dass Ihre Lösung korrekt arbeitet! --- Siehe Ausgabe, Main-Methode der Klasse a3h\BST.java. ## J Beispiel für beste und schlechteste Eingabe für einen BST 1. Geben Sie für die Schlüssel "S C H L U E S S E L K O M P E T E N Z", denen die Zahlen von 0-18 zugeordnet sind, eine beste und eine schlechteste Eingabe für einen BST an. D.h. geben Sie für jeden der beiden Fälle die Reihenfolge der put Operationen an. Sie dürfen die doppelten Schlüssel auslassen. --- + best-case: MECKHSLUOMPTNZ + worst-case: CEHKLMNOPSTUZ 2. Wann gibt es eine eindeutig beste Eingabe für einen BST? In unserem Beispiel gäbe es verschiedene Lösungen für eine beste Eingabe. --- Eine eindeutig beste Eingabe gibt es nur für Bäume mit nur einem Knoten. Für jeden weiteren Knoten kann die Eingabe variieren und das Ergebnis dennoch ein optimaler BST sein. Siehe Beispiel: ``` Eingabe: A A ``` ``` Eingabe: AB A -> A \ B ``` ``` Eingabe: BA B -> B / A ``` ``` Eingabe: BAC B -> B -> B / / \ A A C ``` ``` Eingabe: BCA B -> B -> B \ / \ C A C ``` Alle optimalen Bäume die einen diser Bäume als Teilbaum haben, haben keine optimale Eingabe. ## K Handprotokoll: Bereichsberechnung für einen BST Berechnen Sie für Ihren besten Fall des BST aus J die Schlüsselfolge, die im Bereich "F".."R" liegt. 1. Zeichnen Sie dazu zunächst den BST. ``` M / \ / \ / \ / \ / \ E S / \ / \ / \ / \ C K O U / \ / \ / \ H L N P T Z ``` 2. Zeigen Sie an der Zeichnung durch aussagekräftige Kommentare, den Ablauf der Bereichsberechnung ``` M <-| f < M < r ⇒ M zur Liste hinzufügen / \ | f < M ⇒ recusive nach links / \ | M < r ⇒ recusive nach rechts / \ / \ / \ E S <-| E < r ⇒ recusive nach rechts / \ / \ | f < S ⇒ recusive nach links / \ / \ C K O U <-| f < K < r ⇒ K zur Liste hinzufügen / \ / \ / \ | f < K ⇒ recusive nach links analog -> H L N P T Z | K < r ⇒ recusive nach rechts return -> | f < S < r ⇒ S zur Liste hinzufügen | f < O ⇒ recusive nach links | O < r ⇒ recusive nach rechts ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.