Реализация, временная и пространственная сложность, недостатки и улучшения
Алгоритм
Quicksort — это эффективный и часто используемый алгоритм сортировки.
Он выбирает элемент в качестве опорного и разбивает массив вокруг этого опорного значения на два поддиапазона таким образом, чтобы ни один элемент первого поддиапазона не был больше, чем любой элемент второго поддиапазона. Затем он рекурсивно сортирует поддиапазоны.
Это разделяй и властвуй и алгоритм на месте.
Он имеет наилучший случай и среднюю временную сложность O(n log n), которая ухудшается доO(n²)внаихудшем случае.
Его пространственная сложность в лучшем случае составляет O(log n), а в худшем случае O(n), если только не используется оптимизация хвостового вызова.
Мы реализуем его на Python, проанализируем его временную и пространственную сложность, рассмотрим некоторые его недостатки и обсудим улучшения.
Схема раздела Ломуто
В более простой реализации схема Ломуто выбирает последний элемент массива в качестве опорного:
Весь массив отсортирован по quick_sort(arr, 0, len(arr)-1)
.
Сложность времени
Схема Ломуто имеет временную сложность O(n log n) в среднем и O(n²) в худшем случае.
Худший случай происходит, когда точка разворота постоянно находится далеко от медианы. В частности, когда один из возвращаемых подмассивов имеет размер n − 1 в каждой рекурсии. Затем дерево вызовов состоит из n − 1вложенных вызовов сложностиO(n − i) каждый:
Это тот случай, когда массив отсортирован, отсортирован в обратном порядке или когда все элементы равны.
Ниже приведены среды выполнения для несортированных (синий), отсортированных (красный), отсортированных в обратном порядке (зеленый) и массивов равных элементов (фиолетовый):
Одним из недостатков этой реализации является то, что вероятность наихудшего случая не мала (сортировка уже отсортированного или отсортированного в обратном порядке массива).
Первое улучшение: схема разделения Хоара
Эта схема была оригинальной схемой разделения, разработанной Тони Хоаром.
Он использует два индекса, которые начинаются с обоих концов разделяемого массива. Затем они движутся навстречу друг другу, пока не обнаружат инверсию.
Она более эффективна, чем схема секционирования Ломуто, поскольку в среднем выполняет в три раза меньше свопов и не снижается до O(n²), когда все элементы равны:
Однако, если опорная точка выбрана в качестве первого или последнего элемента, она все равно ухудшится до O(n²) для отсортированных и отсортированных в обратном порядке массивов.
Второе улучшение: выбор поворота
Одно простое улучшение — использовать середину массива вместо последнего элемента:
pivot = arr[(high + low) // 2]
Еще одно решение, позволяющее еще больше снизить вероятность наихудшего случая без слишком больших накладных расходов, заключается в использовании метода среднего из трехметода:
mid = (high + low) // 2 if arr[mid] < arr[low]: arr[mid], arr[low] = arr[low], arr[mid] if arr[high] < arr[low]: arr[high], arr[low] = arr[low], arr[high] # Swap the median estimate in the last position if arr[mid] < arr[high]: arr[mid], arr[high] = arr[high], arr[mid] # Initiate the pivot pivot = arr[high]
Временная сложность для отсортированных и обратно отсортированных массивов теперь снижена до O(n log n).
Вероятность наихудшего случая O(n²) снижается, но все еще существует. Одним из решений может быть использование алгоритма медианы медиан. Он имеет временную сложность O(n) и гарантирует, что точка поворота находится между 30-м и 70-м процентилями. В худшем случае это будет O(n log n). Однако этот метод обычно не используется на практике, так как дополнительные затраты на оценку медианы значительны.
Ниже приведены среды выполнения с использованием схемы разделения Хоара с опорной точкой, выбранной в качестве середины массива:
Мы эффективно сократили временную сложность для отсортированных, обратно отсортированных и массивов равных элементов.
Космическая сложность
Быстрая сортировка имеет пространственную сложность в лучшем случае O(log n) и в худшем случае O(n).
Вышеупомянутое разделение быстрой сортировки на месте использует O(1)дополнительного пространства для хранения информации между каждым рекурсивным вызовом и в лучшем случае делает не болееO(log n) рекурсивных вызовов. которые добавляются в стек вызовов.
Разделение на месте делает быструю сортировку нестабильной, а это означает, что относительный порядок одинаковых элементов не сохраняется.
Как объяснялось выше, в худшем случае быстрая сортировка выполняет (n - 1) рекурсивных вызовов, используя O(n) пробел.
В Python предел рекурсии по умолчанию равен 1000. В худшем случае O(n) вы довольно быстро достигнете предела рекурсии.
Третье улучшение: оптимизация хвостового вызова
Мы можем уменьшить сложность пространства, уменьшив стек вызовов. Это называется оптимизацией хвостового вызова или TCO.
После разделения раздел с наибольшим количеством элементов сортируется с использованием итерации, которая не добавляется в стек вызовов. Другой раздел все еще нужно отсортировать отдельно:
Ниже приведены размеры стека вызовов с TCO (красный) и без (синий):
Заключение
Быстрая сортировка является широко используемым алгоритмом из-за его эффективности. На первый взгляд это может показаться простым, но есть много тонкостей, которые нужно реализовать должным образом.
Вы можете найти полный код, использованный для этой статьи, в моем репозитории GitHub.
Спасибо за прочтение!