Randomisierte Algorithmen und Quicksort Flashcards
1
Q
Was ist eine Indikatorfunktion und wie ist sie definiert?
A
2
Q
Wie funktioniert das inplace randomizen eines unsortierten Arrays?
A
3
Q
Wie funktioniert Quicksort?
A
4
Q
Wie funktioniert die Schlüsselroutine Partition von Quicksort?
A
- Man nimmt den übergebenen Wert p (pivot) als anfang und q als Ende des Teilarrays.
- Man geht jetzt von Punkt p zu jedem Element bis q
- wenn ein Element kleiner ist packt man es eine Stelle vor p. Die nächste Zahl die kleiner als p ist wird zwei stellen vor p gestellt etc. * Am ende wird dann p mit dem Element getauscht, dass als letztes getauscht wurde
- Jetzt sind alle Elemente links von p kleiner als p und alle rechts von p größer
5
Q
Warum nutzt man randomisiertes Quicksort?
A
Quicksort hat einen Worst-Case von O(n^2) um diesen sehr unwahrscheinlich zu machen und nahezu immer eine durchschnittliche Verteilung zu haben wird der Input randomized somit hat man eine erwartete Laufzeit von O(n lg n)
6
Q
Was macht QuickSort zum “besten” Sortieralgorithmus?
A
- QuickSort ist ein guter Mehrzweck-Sortieralgorithmus.
- QuickSort ist in der Regel mehr als doppelt so schnell wie MergeSort
- QuickSort profitiert im wesentlichen von code tuning.
- QuickSort verhält sich auch mit caching und virtuellem Speicher gut
