Какой худший случай сортировки для QuickSort

Худший случай для QuickSort — когда опорный элемент (pivot) всегда выбирается как минимальный или максимальный в подмассиве. Это приводит к несбалансированному разбиению, и время работы деградирует до O(n²).

Пример:

int[] arr = {1, 2, 3, 4, 5}; // Уже отсортированный массив

Если pivot всегда выбирается как первый элемент, разбиение будет:

• (пустой левый подмассив) + [2, 3, 4, 5]
• + [3, 4, 5]
• ...

Решение:

• Выбирать pivot случайно (Randomized QuickSort).
• Использовать медиану трёх (первый, средний, последний элементы).