Какая средняя алгоритмическая сложность быстрой сортировки?

Быстрая сортировка использует стратегию "разделяй и властвуй".

1. Как работает:

• Выбирается опорный элемент (pivot).

• Массив делится на две части: элементы меньше pivot и больше pivot.

• Процесс рекурсивно повторяется для каждой части.

2. Сложность:

• Средний случай: O(n log n) — при хорошем выборе pivot.

• Худший случай: O(n²) — если pivot всегда минимальный или максимальный элемент.

3. Пример на Swift:

func quickSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array }
    let pivot = array[array.count/2]
    let less = array.filter { $0 < pivot }
    let equal = array.filter { $0 == pivot }
    let greater = array.filter { $0 > pivot }
    return quickSort(less) + equal + quickSort(greater)
}

Вывод:
Быстрая сортировка эффективна для больших данных, но требует аккуратного выбора pivot.