SortierAlgorithmen

Question 1

Tafelübung

Insertion Sort

Answer 1

vergleichsbasiertes Verfahren

Beim Einfügen jedes Werts wird die Liste durchlaufen und Wert an entsprechender Stelle eingefügt

Question 2

Tafelübung

Insertion Sort

Komplexität

Answer 2

Worst Case:
Für jeden Wert durch die ganze Liste Laufen
O(n^2)

Average Case:
O(n^2)

best Case:
O(n)

Question 3

Tafelübung

Selection Sort

Answer 3

vergleichsbasiertes Verfahren

Maximum (Minimum) auswählen und in neue Liste einfügen,
wiederholen.

Question 4

Tafelübung

Selection Sort

Komplexität

Answer 4

Worst Case:
jedes Mal muss neues Maximum gefunden werden
O(n^2)

Average Case:
O(n^2)

best Case:
O(n^2)

Question 5

Tafelübung

Vergleichsbasierte Verfahren

Def.

Answer 5

Verfahren, die auf paarweisen Vergleichen von Elementen
basieren
Bestenfalls: O(n log n)

Question 6

Tafelübung

Heap Sort

Def.

Answer 6

Idee: Ein Heap ist die perfekte Datenstruktur, um ein Maximum
(Minimum) zu finden!
1. Heap aufbauen

2. Wiederholen:
   - Maximum (Minimum) entnehmen und
   - Heap-Eigenschaft wiederherstellen

Question 7

Tafelübung

Heap Sort

Komplexität

Answer 7

1. Heap aufbauen: n mal in den Heap einfügen
   O(n log n)
2. n mal das Maximum entnehmen und jeweils die
   Heap-Eigenschaft wiederherstellen
   O(n log n)
   => O(n log n)

Question 8

Tafelübung

Merge Sort

Answer 8

»Easy split, hard join.«

Zeitkomplexität:
O(n log n)

Question 9

Tafelübung

Quick Sort

Answer 9

Prinzip:
Split:
Ein Pivot-Element p auswählen,
die Liste in zwei Teil-Listen aufteilen (kleiner gleich p und größer gleich p)

rekursiv weitermachen

dann (ist sortiert) zusammenfügen

Question 10

Tafelübung

Quick Sort

Komplexität

Answer 10

Optimalfall:
Halbierung in jedem Schritt
O(log n) Ebenen à O(n)
=> O(n log n)

Schlechtester Fall:
Liste schrumpft in jedem Schritt um 1-> n Ebenen
=> O(n2)

Durchschnitt:
=> O(n log n)

Question 11

Tafelübung

Quick Sort: Implementierung Struktur

Answer 11

Quick Sort: Implementierung
Struktur ist aber immer die gleiche:

1. Pivot-Element auswählen
   Bei manchen Implementierungen muss ein bestimmtes
   Pivot-Element (z. B. das in der Mitte) verwendet werden,
   andere sind freier.
2. Liste/Feld aufteilen
   Der schwierige Teil.
   Implementierungen unterscheiden sich z. T. stark.
3. Teil-Listen rekursiv sortieren

Question 12

Tafelübung

Implementierung - QuickSort mit partition

Answer 12

void quicksort(int[] a) {
    quicksort(a, 0, a.length);
}
void quicksort(int[] a, int low, int high) {
    if (high - low <= 1) {
        return;
    }
    int pivot = a[low];
    int n = partition(a, low, high, pivot);
    quicksort(a, low, n);
    quicksort(a, n+1, high);
}

Question 13

KLAUSURAUFGABE SS18

Was ist der Unterschied zwischen vergleichsbasierten und nicht vergleichsbasierten Sortier- Algorithmen bezüglich ihrer Laufzeit-Komplexität?

Answer 13

eigene Lösung

Vergleichsbasierte Verfahren O(n log n)

nicht-vergleichsbasierte Verfahren O(n+m / n*k)

Question 14

KLAUSURAUFGABE SS18

Zu welcher Komplexitätsklasse gehören die schnellsten Sortier-Algorithmen, wenn die Daten
in folgenden Datenstrukturen vorliegen, aber sonst nichts über die Daten bekannt ist?
• lineare, unsortierte verkettete Liste:
• unsortierte Reihung (Array):
• Halde:

Answer 14

1. QuickSort & MergeSort O(n log n)
2. QuickSort & MergeSort O(n log n)
3. Fangfrage weil Halde nicht sortiert…
   Genauso QuickSort, MergeSort O(n log n)

(HeapSort ?)

Question 15

KLAUSURAUFGABE WS17

Welche Aussage(n) trifft/treffen auf den Quick-Sort-Algorithmus zu

1. Der Index der Pivot-Variablen muss immer in der Mitte des Feldes, das
   sortiert werden soll, liegen.
2. Der Wert der Pivot-Variablen muss immer der Mittelwert der Werte der
   Elemente, die sortiert werden sollen, sein.
3. Der Wert der Pivot-Variablen muss immer der Median der Werte der
   Elemente, die sortiert werden sollen, sein.
4. Eine besonders günstige Aufteilung des zu sortierenden Feldes erhält
   man, wenn bei jeder Teilung ein Teilfeld mit nur einem Element entsteht,
   das bereits sortiert ist.
5. Eine besonders günstige Aufteilung des zu sortierenden Feldes erhält
   man, wenn etwa gleich große Teilfelder entstehen, die aber nicht bereits
   sortiert sein müssen.

Answer 15

eigene Lösung

1. falsch
2. falsch
3. falsch
4. falsch
5. richtig

Question 16

KLAUSURAUFGABE WS17

Welche Aussage(n) trifft/treffen auf das sogenannte Radix-Sortieren zu?

1. Ein Behälter kann beliebig viele Schlüssel aufnehmen. Dies kann beispielsweise
   mit einer verketteten Liste pro Behälter implementiert werden.
2. Es gibt exakt genau so viele Behälter wie es Schlüssel gibt.

Answer 16

eigene Lösung

1. richtig
2. falsch

Question 17

KLAUSURAUFGABE SS17

Welche Aussagen bzgl. Sortierverfahren sind richtig?

Die Haldensortierung (HeapSort) verbessert das einfache Sortieren durch Auswählen (SelectionSort) durch Anordnung der zu sortierenden Elemente in einer Halde (Heap).

HeapSort teilt die zu sortierende Folge in einen Haldenbereich und einen bereits sortierten
Bereich auf und ist damit ein typischer Vertreter der divide & conquer-Verfahren.

Die Wiederherstellung der Heap-Eigenschaft nach der Entnahme des Maximums dauert
O(log n).

Answer 17

1. richtig
2. falsch
3. richtig

Question 18

KLAUSURAUFGABE WS16

Welche Aussagen bzgl. Sortierverfahren sind richtig?

Die Haldensortierung (HeapSort) verbessert das einfache Sortieren durch Auswählen (SelectionSort) durch Anordnung der zu sortierenden Elemente in einer Halde (Heap).

HeapSort teilt die zu sortierende Folge in einen Haldenbereich und einen bereits sortierten
Bereich auf und ist damit ein typischer Vertreter der divide & conquer-Verfahren.

Die Wiederherstellung der Heap-Eigenschaft nach der Entnahme des Maximums dauert
O(log n).

Answer 18

1. richtig
2. falsch
3. richtig

Question 19

KLAUSURAUFGABE SS16

Zu welcher Komplexitätsklasse gehören die schnellsten in der Vorlesung behandelten Sortier- Algorithmen, wenn die Daten in folgenden Datenstrukturen vorliegen, aber sonst nichts über
die Daten bekannt ist?

• lineare, unsortierte verkettete Liste:
• unsortierte Reihung (Array):
• Halde:

Answer 19

1. QuickSort & MergeSort O(n log n)
2. QuickSort & MergeSort O(n log n)
3. Fangfrage weil Halde nicht sortiert…
   Genauso QuickSort, MergeSort O(n log n)

(HeapSort ?)

Question 20

KLAUSURAUFGABE SS16

Aus welchen drei Schritten besteht ein Algorithmus nach dem Divide-and-Conquer-Prinzip?
Nennen Sie diese Schritte und beschreiben Sie kurz, was im Quicksort-Algorithmus in jedem
dieser Schritte abläuft. In welchem Schritt wird die eigentliche Arbeit verrichtet?

Answer 20

1. split: Aufteilen des Problems
   Split:
   Ein Pivot-Element p auswählen,
   die Liste in zwei Teil-Listen aufteilen: kleiner gleich und größer gleich pivot
2. Rekursives Lösen der Teilprobleme
   Die Liste ist schon ein bisschen »sortierter« als vorher
   -> (rekursiv) weitermachen!
3. join: Zusammenführen der Teillösungen
   am Ende zusammenfügen

Question 21

KLAUSURAUFGABE WS 15

Welche der folgenden Komplexitätsklassen gibt das beste im Mittel (average case) erreichbare
asymptotische Verhalten für nicht vergleichsbasiertes Sortieren an?

Answer 21

eigene Lösung

O(n^2)

Question 22

KLAUSURAUFGABE WS 15

Welche der folgenden Komplexitätsklassen gibt das beste im Mittel (average case) erreichbare
asymptotische Verhalten für vergleichsbasiertes Sortieren an?

Answer 22

eigene Lösung

O(n log n)

Question 23

KLAUSURAUFGABE WS 14

Welche Aussage(n) trifft/treffen auf das sogenannte Radix-Sortieren zu?

1. Ein Behälter kann beliebig viele Schlüssel aufnehmen. Dies kann beispielsweise
   mit einer verketteten Liste pro Behälter implementiert werden.
2. Wird durch Löschen von Elementen ein Behälter leer, dann genügt es,
   diesen als frei zu markieren.
3. Um aus n Schlüsseln den Richtigen aufzufinden werden im Worst-Case
   nicht weniger als O(n log(n)) Operationen benötigt.
4. Es gibt exakt genau so viele Behälter wie es Schlüssel gibt.

Answer 23

1. richtig
2. richtig
3. falsch
4. falsch

Question 24

KLAUSURAUFGABE SS15 Welche Aussage(n) trifft/treffen auf den Quick-Sort-Algorithmus zu

1. Der Index der Pivot-Variablen muss immer in der Mitte des Feldes, das
   sortiert werden soll, liegen.
2. Der Wert der Pivot-Variablen muss immer der Mittelwert der Werte der
   Elemente, die sortiert werden sollen, sein.
3. Der Wert der Pivot-Variablen muss immer der Median der Werte der
   Elemente, die sortiert werden sollen, sein.
4. Eine besonders günstige Aufteilung des zu sortierenden Feldes erhält
   man, wenn bei jeder Teilung ein Teilfeld mit nur einem Element entsteht,
   das bereits sortiert ist.
5. Eine besonders günstige Aufteilung des zu sortierenden Feldes erhält
   man, wenn etwa gleich große Teilfelder entstehen, die aber nicht bereits
   sortiert sein müssen

Answer 24

eigene Lösung

1. falsch
2. falsch
3. falsch
4. falsch
5. richtig

Question 25

KLAUSURAUFGABE SS15 Welche Aussage(n) trifft/treffen auf das sogenannte Radix-Sortieren zu? 1. Ein Behälter kann beliebig viele Schlüssel aufnehmen. Dies kann beispielsweise mit einer verketteten Liste pro Behälter implementiert werden. 2. Es gibt exakt genau so viele Behälter wie es Schlüssel gibt.

Answer 25

eigene Lösung 1. richtig 2. falsch