Time and Space Complexity

Временная сложность:

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

Пространственная сложность:

• O(n) для версии, которую мы создаем здесь, так как на каждом шаге мы создаем новые списки меньшего и большего размера. Классическая in-place (на месте) Quick Sort улучшает этот показатель до O(log n) дополнительного пространства.

Резюме:

• Quick Sort очень быстра в среднем и является основным алгоритмом сортировки на практике.
• Плохой выбор опорного элемента может снизить производительность до O(n²); хорошие стратегии выбора опорного элемента (например, выбор случайного или медианного элемента) позволяют этого избежать.