Algorytmy i struktury danych · Senior · Pytanie 32 z 75
Czym jest introsort i dlaczego używa go C++ std::sort?
- ✓Poprawna odpowiedź: Quicksortem, który przechodzi na heapsort, gdy rekurencja jest za głęboka
- 2Sortowaniem, które wybiera algorytm według typu danych
- 3Sortowaniem przez scalanie ze wstawianiem na każdym poziomie
Wyjaśnienie
Quicksort jest szybki średnio, ale jego najgorszy przypadek O(n²) można sprowokować. Introsort ogranicza głębokość rekurencji do około 2 log n i przechodzi na heapsort, gwarantując O(n log n) i zachowując szybkość quicksorta.