Wie funktioniert Quicksort?
Wie funktioniert die Partitionierung von Quicksort?
Welche Laufzeit hat Quicksort, wenn die Aufteilung immer in einem festen Verhältnis
erfolgt, z.B. immer im Verhältnis 9:1? (mit Herleitung
Welche Laufzeit hat Quicksort im mittleren Fall? Skizzieren Sie, wie man zu diesem
Ergebnis kommt
Welche Worst-Case-Laufzeit hat Quicksort und für welche Folgen wird diese tats¨achlich
erreicht?
Worst-Case-Laufzeit ist O(n^2)
stark vorsortierte Folgen oder solche Folgen, die viele gleiche Elemente enthalten
Wie können wir Quicksort verbessern für den Fall, dass die Folgen stark vorsortiert
sind?
Wie können wir Quicksort verbessern für den Fall, dass viele gleiche Werte zu sortieren
sind? Erklären Sie den Algorithmus.
Wie groß ist die Rekursionstiefe bei Quicksort im worst-case und wie können wir die
Rekursionstiefe beschränken
Welche Sortierverfahren sortieren im worst-case in Zeit O(n · log n)?
Mergesort
Heapsort
Erklären Sie Mergesort und geben Sie die Rekursionsgleichung an
Skizzieren Sie die Funktionsweise von Heapsort und leiten Sie die Laufzeit her. Wie
lange dauert das Aufbauen eines initialen Heaps und wie geht das?
Erstelle einen initialen Max-Heap. Anschließend wird in Runde k das oberste Element
mit dem Element an Position n − k getauscht und das nun oberste Element versickert.
Es werden n Runden benötigt, jeweils mit der Laufzeit O(log n), da der Heap nur loga-
rithmische Tiefe hat. Aufbauen des initialen Heaps erfolgt in Zeit O(n).
Das Erstellen des initialen Heaps erfolgt, indem wir die Elemente k(n/2−1), . . . , k_0 nach-
einander versickern lassen. Dabei müssen n/4 Elemente nur um eine Ebene im Baum
verschoben werden, n/8 viele Elemente nur um 2 Ebenen usw
Was ist ein allgemeines Sortierverfahren und welche untere Schranke gilt für solche
allgemeinen Sortierverfahren?
Allgemeine Sortierverfahren verwenden ausschließlich Vergleichsoperationen zwi-
schen Schlüsseln, um die Positionen der Werte in der sortierten Folge zu bestimmen, aber
keine arithmetischen Operationen oder ähnliches.
Jedes allgemeine Sortierverfahren benötigt zum Sortieren von n verschiedenen Schlüsseln im
schlechtesten Fall und im Mittel wenigstens Ω(n · log(n)) Schlüsselvergleiche.
Skizzieren Sie die Herleitung der unteren Schranke für allgemeine Sortierverfahren.
Was versteht man unter einem stabilen Sortierverfahren?
Gleiche Elemente stehen nach dem Sortieren in der gleichen relativen Reihenfolge
zueinander wie vor dem Sortieren
Welche Laufzeit hat Counting-Sort? Erläutern Sie die Bedeutung der Variablen und
begründen Sie Ihre Angabe.
O(n + k) bei n Elementen und k Schlüsselwerten.
• Initialisieren des Count-Arrays: O(k)
• Durchlaufen der Werte zum Erstellen der Counts: O(n)
• Count aufsummieren: O(k)
• Einsortieren der Werte: O(n)
Welche der folgenden Aussagen sind richtig und welche sind falsch? Für jede falsch
beantwortete Frage wird eine korrekt beantwortete Frage nicht bewertet.
Nur richtige ankreuzen Nummerierung von oben nach unten.
Wie funktioniert Radix-Sort?
Sortiere die Zahlen anhand der einzelnen Ziffern, beginnend mit der niederwertigsten
Stelle. Verwende ein stabiles Sortierverfahren wie Countingsort. Falls nötig, müssen führende
Nullen eingefügt werden. Dieser Ansatz ist für ganze Zahlen geeignet, aber nicht für reelle
Zahlen, da es überabzählbar viele reelle Zahlen gibt
Welche Laufzeit hat Radix-Sort? Erläutern Sie die Bedeutung der Variablen und begründen Sie Ihre Angabe.
Welche Laufzeit hat Bucket-Sort? Skizzieren Sie die Herleitung bzw. begründen Sie Ihre
Angaben.
Last changed2 months ago
