Alles Flashcards
Nenne drei typische Sortieralgorithmen
Selection Sort Insertion Sort Merge Sort
Erkläre den Ablauf von Selection Sort
- Beginne den Algorithmus mit dem Index i = 1 2. Durchlaufe dazu alle Elemente der Folge von i bis n und identifiziere den Index j, an dem das kleinste Element steht (3. Das kleinste Element kann bereits am Index i stehen, in diesem Fall entspricht der Index j dem Index i) 4. Tausche das Element an Index i gegen das Element an Index j 5. Ergebnis: Das kleinste Element steht nun an der ersten Stelle der Folge i=2; i=2… i=n-1 6. Wiederhole den beschriebenen Ablauf für Index
Wie ist das Laufzeitverhalten des Selection Sorts? Wie berechnet es sich?
Erster Vergleich (i=1) vergleicht N-1 Mal (Vergleich nicht mit sich selbst). Zweiter Vergleich (i=2) vergleicht N-2 Mal (Vergleich nicht mit sich selbst und nicht vorherigen). … Ergebnis: 1+2+3+4…N-1 Mal Durch Gauß: (N²-N)/2 –> Quadratisch
Erkläre den Ablauf von Insertion Sort
- Die Zielfolge enthält initial das erste Element der Folge und ist somit sortiert (da lediglich einelementig) 2. Beginne den Algorithmus mit dem Index i = 2 3. Durchlaufe alle Elemente der Folge von 0 bis i und identifiziere den Index j, an dem das Element an Index i einzufügen ist 4. Füge das Element an Index i am Index j ein und verschiebe alle Elemente von Index j bis i-1 um einen Index nach rechts 5. Ergebnis: Die Indices 0 bis i sind sortiert (Zielfolge) 6. Wiederhole den beschriebenen Ablauf für Index i=3, i=4 , … , i=N
Wie ist das Laufzeitverhalten des Insertion Sorts? Wie berechnet es sich?
Schlüsselvergleiche: Im besten Fall N-1 , im schlechtesten Fall ungefähr N²/2, im Mittel ungefähr N²/4 Austauschoperationen: Im besten Fall 0, im schlechtesten Fall ungefähr N²/2, im Mittel ungefähr N²/4 –> Quadratisch
Erkläre den Ablauf von Merge Sort
Idee: Zu sortierende Folge in zwei kleinere Folgen aufteilen, diese jeweils rekursiv sortieren und die (sortierten) Ergebnisfolgen per Mischen wieder zusammenfassen Verfahren terminiert, da wiederholtes Aufteilen der Folge irgendwann zu einelementigen Folgen führt, die von Natur aus sortiert sind (Abbruchfall) Ablauf Ist die Folge f leer oder einelementig, stellt sie bereits eine sortierte Folge dar und das Verfahren ist abgeschlossen (Ergebnis: f) Enthält die Folge f hingegen mehr als ein Element, so zerlege sie in der Mitte in zwei Teilfolgen fl und fr(deren Länge sich höchstens um 1 unterscheidet) Sortiere die beiden Teilfolgen fl und fr rekursiv (Ergebnisfolgen fl’ und fr’) Mische die beiden sortierten Folgen fl’ und fr’ zur sortierten Folge f’
Wie ist das Laufzeitverhalten des Merge Sorts? Wie berechnet es sich?
Laufzeitverhalten? Anzahl Schritte? Algorithmus bildet über die wiederholte Halbierung log2(N) Ebenen Für jede Ebene müssen beim Mischen mindestens 1/2 N und schlimmstenfalls N-1 Vergleiche durchgeführt werden Schlüsselvergleiche Im besten Fall 1/2*N* Log2(N), im schlechtesten Fall N* Log2(N) Laufzeitverhalten näherungsweise N* Log2(N) => schlechter als linear, besser als quadratisch => auch als linearithmetisches Laufzeitverhalten bezeichnet Speicherverhalten? Typischerweise Out-of-Place-Sortieren, d.h. Erzeugung neuer Datenstrukturen in Abhängigkeit von N (hier des temporären Arrays beim Mischen) zusätzlicher Speicher in Höhe von N erforderlich
Wie sieht die Klasse “MyRBSet” aus?
public class MYRBSet<e>><br></br>implements GenericOrderedSet<e>{</e></e>
private static class TreeNode<t>{<br></br>private T key;<br></br>private boolean red;<br></br>private TreeNode<t> left;<br></br>private TreeNode<t> right;</t></t></t>
private TreeNode{T key, boolean red, TreeNorde<t> left, TreeNode<t> right){<br></br>this.key = key;<br></br>this.red = red;<br></br>this.left = left;<br></br>this.right = right;</t></t>
}
}
private TreeNode<e> root;</e>
}
Wie sieht die lookup/contains-Operation im Binären Suchbaum (und damit auch bei Rot-Schwarz-Bäumen) aus?
In welcher Laufzeitkomplexität arbeitet diese?
Laufzeit 0(H), wobei H die Baumhöhe darstellt.
private TreeNode<e> lookup(TreeNode<e> t, E key){</e></e>
if (t == null){
return null;
}
int cmp = key.compareTo(t.key);
if (cmp \< 0){
return lookup(t.left, key);
} else if (cmp \> 0){
return lookup(t.right, key);
} else {
return t;
}
}
@Override
public boolean contains(E key){
return lookup(this.root, key) != null;
}
Wie wird rotateLeft bei Schwarz-Rot-Bäumen implementiert?
private TreeNode<e> rotateLeft(TreeNode<e> t){</e></e>
TreeNode<e> r = t.right;<br></br><br></br>t.right = r.left;<br></br>r.left = t;<br></br><br></br>r.red = t.red;<br></br>t.red = true;</e>
return r;
}
Wie wird das Umfärben (Elternknoten rot, Kindknoten schwarz) im Rot-Schwarz-Baum genannt und wie wird dies implementiert?
private TreeNode<e> flip(TreeNode<e> t){</e></e>
t. red = true;
t. left.red = false;
t. right.red = false;
return t;
}
Wie wird rotateRight im Rot-Schwarz-Baum implementiert?
private TreeNode rotateRight (TreeNode t){
TreeNode l = t.left;
t. left = l.right;
l. right = t;
l. red = t.red;
t. red = true;
return l;
}
Wie sieht die Insert-Funktion beim Rot-Schwarz-Baum aus?
private TreeNode insert(TreeNode t, E key){
if (t == null){
return new TreeNode(key, true, null, null);
}
int cmp = key.compareTo(t.key);
if(cmp \< 0){
t.left = insert(t.left, key);
} else if (cmp \> 0){
t.right = insert(t.right, key);
}else {
return t;
}
if (isRed(t.right) && !isRed(t.left)){
t = rotateLeft(t);
}
if(isRed(t.left) && isRed(t.left.left){
t= rotateRight(t);
}
if(isRed(t.left) && isRed(t.right)){
t = flip(t);
}
return t;
}
private Boolean isRed(TreeNode t){
return t != null && t.red;
}
Wie sieht die Klasse MyLinked List in ProgrammCode aus?
public class MyLinkedList implements GenericList{
private static class ListNode{
private T value;
private ListNode<t> next = null;<br>private ListNode(T value; ListNode<t> next){<br>this.value = value;<br>this.next = next;<br>}</t></t>
}
private ListNode first = new ListNode<e>(null, null);<br></br>}</e>
Wie sieht bei MyLinkedList die Insert-Funktion aus?
public MyLinkedList insert(E value, int idx){
ListNode<e> curr = this.first;<br></br>while(idx-- > 0){<br></br>curr = curr.next;<br></br>}<br></br>curr.next = new ListNode<e>(value, curr.next);<br></br>return this;<br></br>}</e></e>
Wie sieht die remove-Funktion bei verketteten Listen aus?
@Override
public E remove(int idx){
E removed = null;
ListeNode curr = this.first;
while (idx– > 0){
curr = curr.next;
}
removed = curr.next.value;
curr.next = curr.next.next;
return removed;
}
Wie wird in der Verketteten Liste (MyLinkedList) indexOf implementiert?
Was muss als erstes gemacht werden?
Erst das Startelement nehmen und durchlaufen, bis Start-Index gefunden
Wieso werden Heaps (Array) nicht für binäre Suchbäume genutzt?
Binäre Suchbäume sind nicht immer vollständig belegt, weshalb es zu exponentiellem Speicherbedarf kommen würde. Siehe dazu Grafik.
Außerdem können Transformationen (bspw Rotationen) problematisch werden.
Wie ermittelt heapify die Indices, bis zu denen er die heap-Eigenschaften prüfen muss?
(heap_size / 2)-1 bis 0
