Алгоритми та структури даних · Senior · Запитання 32 з 75
Що таке introsort і чому його використовує C++ std::sort?
- ✓Правильна відповідь: Quicksort, що переходить на heapsort, коли рекурсія стає задовгою
- 2Сортування, що обирає алгоритм за типом даних
- 3Злиття, що використовує вставки на кожному рівні
Пояснення
Quicksort швидкий у середньому, але його найгірший випадок O(n²) можна спровокувати. Introsort обмежує глибину рекурсії приблизно 2 log n і переходить на heapsort, гарантуючи O(n log n) і зберігаючи швидкість quicksort.