Algorithmen und Datenstrukturen · Senior · Frage 32 von 75
Was ist Introsort, und warum nutzt C++ std::sort es?
- 1Quicksort, das bei zu tiefer Rekursion auf Heapsort umschaltet
- 2Ein Sortierverfahren, das den Algorithmus nach dem Datentyp wählt
- 3Merge Sort, das auf jeder Ebene Insertion Sort nutzt
Antwort zeigen
Richtige Antwort: Quicksort, das bei zu tiefer Rekursion auf Heapsort umschaltet
Erklärung
Quicksort ist im Schnitt schnell, aber sein schlimmster Fall O(n²) lässt sich auslösen. Introsort begrenzt die Rekursionstiefe auf etwa 2 log n und wechselt zu Heapsort, was O(n log n) garantiert und das Tempo von Quicksort behält.