Informatik Algorithmen – Quicksort und Partitionierung
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was ist die Grundidee von Quicksort? · Wie funktioniert das Lomuto-Partitionierungssc…
Karten
15 KartenWas ist die Grundidee von Quicksort?
Rückseite
Teile-und-Herre: Wähle ein Pivot, partitioniere das Array so, dass kleinere Elemente links, größere rechts stehen, dann rekursiv beide Teilarrays sortieren.
Wie funktioniert das Lomuto-Partitionierungsschema?
Rückseite
Pivot ist letztes Element; Index i trennt ≤-Pivot-Bereich; iteriere mit j, tausche bei ≤ Pivot arr[i++] mit arr[j]; am Ende Pivot mit arr[i] tauschen.
Wie funktioniert das Hoare-Partitionierungsschema?
Rückseite
Zwei Pointer von links und rechts; linker sucht ≥ Pivot, rechter ≤ Pivot; bei Überkreuzung stoppen; tausche gefundene Elemente; effizienter als Lomuto.
Welche Pivot-Strategien vermeiden den Worst-Case O(n²)?
Rückseite
Median-of-three (Erster, Mitte, Letzter), zufälliges Pivot oder Median-of-Medians garantieren mit hoher Wahrscheinlichkeit O(n log n) Laufzeit.
Warum ist Quicksort instabil?
Rückseite
Gleiche Schlüssel können durch Partitionierung ihre relative Reihenfolge ändern, da Elemente über weite Distanzen getauscht werden (z. B. Pivot mit letztem ≤-Element).
Wie lautet die Rekursionstiefe im Durchschnittsfall?
Rückseite
O(log n), da das Array bei guter Pivot-Wahl jeweils etwa halbiert wird; im Worst-Case (sortiertes Array + schlechtes Pivot) O(n).
Was bewirkt Tail-Recursion-Optimierung bei Quicksort?
Rückseite
Der rekursive Aufruf für das größere Teilarray wird durch Iteration ersetzt, der für das kleinere bleibt rekursiv – Stapeltiefe sinkt auf O(log n).
Ab welcher Arraygröße lohnt sich Insertion-Sort als Basisfall?
Rückseite
Typisch 10–20 Elemente: Insertion-Sort hat geringeren Overhead für kleine Arrays und verbessert Cache-Lokalität im Quicksort-Hybrid.
Was ist 3-Way-Partitionierung (Dutch National Flag)?
Rückseite
Teilt Array in < Pivot, = Pivot, > Pivot; optimal bei vielen Duplikaten, reduziert Vergleiche auf Θ(n) statt O(n log n) bei Gleichheit.
Wie wählt Introsort das Pivot und vermeidet Worst-Case?
Rückseite
Kombiniert Quicksort mit Heapsort: bei Rekursionstiefe > 2 log n wechselt es zu Heapsort, garantiert O(n log n) Worst-Case.
Warum ist Quicksort cache-effizienter als Mergesort?
Rückseite
In-place-Partitionierung arbeitet sequenziell im Speicher, nutzt CPU-Cache optimal; Mergesort benötigt zusätzlichen Speicher und springt zwischen Arrays.
Was passiert bei Quicksort mit vielen identischen Schlüsseln ohne 3-Way-Partition?
Rückseite
Degeneriert zu O(n²), da Partitionierung extrem unausgewogen wird (ein Teilarray fast leer, anderes fast komplett).
Wie berechnet man den Median-of-three Pivot?
Rückseite
Vergleiche erstes, mittleres und letztes Element; wähle den medianen Wert als Pivot; tausche ihn an Array-Ende für Lomuto oder an Anfang für Hoare.
Welche Invariante gilt während der Hoare-Partitionierung?
Rückseite
Alle Elemente links von linkem Pointer ≤ Pivot, alle rechts von rechtem Pointer ≥ Pivot; Pointer bewegen sich aufeinander zu bis Überkreuzung.
Was ist der Unterschied zwischen Quicksort und Quickselect?
Rückseite
Quickselect nutzt Partitionierung wie Quicksort, rekursiert aber nur in den Bereich, der das k-te Element enthält – Durchschnitt O(n) statt O(n log n).