Как оценивается эффективность алгоритма быстрой сортировки в зависимости от ситуации?

Эффективность алгоритма быстрой сортировки (QuickSort) зависит от выбора опорного элемента и структуры данных:

• Среднее время: O(n log n) — при случайном или хорошо подобранном опорном элементе.
• Худшее время: O(n²) — если опорный элемент всегда выбирается неудачно (например, самый большой или самый маленький элемент в отсортированном массиве).

В практике для улучшения эффективности часто используют случайный выбор опорного элемента или медиану из нескольких элементов.

QuickSort обычно быстрее других алгоритмов сортировки благодаря хорошей локальности данных и низким накладным расходам, но для очень маленьких массивов или почти отсортированных данных иногда предпочтительнее вставками или сортировка слиянием.

Пример выбора опорного элемента:

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // простой выбор последнего элемента
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

Для улучшения можно выбирать случайный pivot или медиану из трёх элементов.