Algorithmen und Datenstrukturen · Senior · Frage 58 von 75
Warum ist die Rekursionstiefe von Quicksort ein Problem, und wie begrenzt man sie?
- 1Schlechte Pivots ergeben Tiefe n; in die kleinere Seite rekursieren
- 2Tiefe Rekursion macht das Sortieren bei gleichen Schlüsseln instabil
- 3Die Tiefe ist immer log n, also nie ein Problem
Antwort zeigen
Richtige Antwort: Schlechte Pivots ergeben Tiefe n; in die kleinere Seite rekursieren
Erklärung
In die kleinere Partition zu rekursieren und über die größere zu iterieren garantiert eine Stack-Tiefe von O(log n), auch wenn die Zeit sich verschlechtert. Introsort begrenzt die Tiefe zusätzlich und wechselt zu Heapsort.