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
Wie wird insert bei “MyArrayList” implementiert?
public MyArrayList insert(E value, int idx){
E[] new_vals = (E[]) new Object[this.vals.length + 1];
System.arraycoppy(this.vals, 0, new_vals, 0, idx);
System.arraycopy(this.vals, idx, new_vals, idx +1, this.vals.length - idx);
new_vals[idx] = value;
this.vals = new_vals;
return this;
}
Was wird bei der MyArrayList bei der Methode remove zurückgegeben? Findet hier auch eine Verkleinerung des Arrays statt?
Es wird das entfernte Element E zurückgegeben:
public E remove(int idx)
Das Array wird verkleinert.
Beschreibe die wesentlichen Unterschiede der MyFastArrayList für die Methode insert im Vergleich zur MyArrayList
public MyFastArrayList insert(E value, int idx){
if(this.used == this.vals.length){
E[] new_vals = (E[]) new Object[this.vals.length + MyFastArrayList.block];
System.arraycopy(this.vals, 0, new_vals, 0, idx);
System.arraycopy(this.vals, idx, new_vals, idx+1, this.vals.length - idx)
new_vals[idx] = value;
} else{
System.arraycopy(this.vals, idx, this.vals, idx+1, this.used - idx);
this.vals[idx] = value;
}
this.used++;
return this;
}
Wie sieht die MyFastArrayList-Klasse aus?
public class MyFastArrayList<e> implements GenericList<e>{<br></br>private final static int block = 100;<br></br>private int = 0;<br></br>private E[] vals = (E[]) new Object[MyFastArrayList.block];</e></e>
}
Wie wird die MyRecursiveList implementiert?
public class MyRecursiveListNode<e> implements GenericRecursiveList<e>{</e></e>
private E value;
private GenericRecursiveList<e> next = null;</e>
public MyRecursiveListNode(E value, GenericRecursiveList<e> next){<br></br>this.value = value;<br></br>this.next = next;<br></br>}</e>
}
Wie ist bei der MyRecursiveList die insert-Methode implementiert?
@Override
public GenericRecursiveList<e> insert(E value, int idx){<br>if (idx==0){<br>return new MyRecursiveListNode(value, this);<br>} else {<br>this.next = this.next.insert(value, idx-1);<br>return this;<br>}<br>}</e>Was ist der Unterschied zwischen der MyFastArrayList und der MyFastDSArrayList?
Bei der MyFastArrayList gibt es einen Block, um den die Länge erhöht wird. Bei der DS ist es ein Prozentsatz.
}
if(idx < (this.length / 2){
while (idx-- > 0){
curr = curr.next;
}
ListNode
curr.next.prev = newnode;
curr.next=newnode;
} else{
while (idx++ < this.length){
curr = curr.prev;
}
...
}
++this.length;
return this;
}
private int lookup(E key){
int low = 0;
int high = this.used - 1:
int mid = low + (high - low)/2;
while (low <= high){
if(key.compareTo(this.vals[mid] == 0){
return mid;
}
if(key.compareTo(this.vals[mid] > 0){
low = mid + 1;
} else {
high = mid - 1;
}
mid = low + (high- low)/2;
}
return -1;
}
}
private static class BucketNode
private T key;
private BucketNode
private BucketNode(T key, BucketNode
this.key = key;
this.next = next;
}
private final static int init_buckets = 256;
private final static double load_factor = 0,5;
private BucketNode
new BucketNode[MyHashSet.init_buckets];
private int size = 0;
private int hash(E key, int M){
return Math.abs(key.hashCode() % M);
}
/*...*/
}
BucketNode new_buckets = new BucketNode[new_length]:
for(int i = 0; i < old_buckets.length; i++){
BucketNode
while(src != null){
E key = src.key;
addToTable(new_buckets, key);
src = src.next;
}
}
return new_buckets;
}
int hash = hash(key, buckets.length);
BucketNode
while(cn != null && !key.equals(cn.key)){
cn = cn.next;
}
return cn != null;
}
int hash = hash(buckets, key);
BucketNode
return 1;
} else if(!cn.key.equals(key)){
while(cn.next != null && !cn.next.key.equals(key)){
cn = cn.next;
}
if(cn.next == null){
cn.next = new BucketNode(key, null);
return 1;
}
int hash = hash(key, buckets.length);
BucketNode
if(cn == null){
return 0;
} else if(cn.key.equals(key)){
buckets[hash] = cn.next;
return 1;
};
while(cn.next != null && !cn.next.key.equals(key){
cn = cn.next;
}
if(cn.next == null){
return 0;
} else{
cn.next = cn.next.next;
return 1;
}
}
}
