Алгоритми та структури даних · Middle · Запитання 3 з 75
Який найгірший випадок швидкого сортування і коли він трапляється?
- ✓Правильна відповідь: O(n²), коли опорні раз у раз ділять масив нерівно
- 2O(n log n), коли в масиві багато дублікатів
- 3O(n), коли вхідні дані вже відсортовані
Пояснення
Якщо опорний елемент завжди найменший чи найбільший (наприклад, перший елемент відсортованого масиву), кожне розбиття відокремлює лише один елемент. Випадковий опорний або медіана трьох роблять це малоймовірним; у середньому O(n log n).