Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 11.11 Резюме

### 1. Ключевые выводы

- Сортировка пузырьком выполняет сортировку за счет обмена соседних элементов. Если добавить флаг для досрочного выхода, лучшую временную сложность пузырьковой сортировки можно оптимизировать до \(O(n)\) .
- Сортировка вставками на каждом раунде вставляет элемент из неотсортированного диапазона в правильную позицию внутри отсортированного диапазона. Хотя ее временная сложность равна \(O(n^2)\) , она очень популярна для задач сортировки небольших массивов, поскольку число элементарных операций у нее сравнительно невелико.
- Быстрая сортировка основана на операции разделения с опорным элементом. При неудачном выборе опорного элемента на каждом раунде ее временная сложность может деградировать до \(O(n^2)\) . Использование медианы трех элементов или случайного опорного элемента уменьшает вероятность этой деградации. Если всегда рекурсивно обрабатывать более короткий поддиапазон первым, можно эффективно уменьшить глубину рекурсии и оптимизировать пространственную сложность до \(O(\log n)\) .
- Сортировка слиянием включает этапы разделения и слияния и служит типичным проявлением стратегии «разделяй и властвуй». Для сортировки массива ей требуется вспомогательный массив, поэтому пространственная сложность равна \(O(n)\). Однако при сортировке связного списка пространственную сложность можно оптимизировать до \(O(1)\) .
- Блочная сортировка включает три этапа: распределение данных по блокам, сортировку внутри блоков и объединение результатов. Она тоже отражает стратегию «разделяй и властвуй» и подходит для очень больших объемов данных. Ключ к эффективности блочной сортировки - равномерное распределение данных.
- Сортировка подсчетом является частным случаем блочной сортировки. Она реализует сортировку через подсчет числа вхождений данных. Сортировка подсчетом подходит для случаев, когда объем данных велик, но диапазон значений ограничен, и при этом данные можно преобразовать в положительные целые числа.
- Поразрядная сортировка выполняет сортировку данных путем последовательной сортировки по каждому разряду и требует, чтобы данные можно было представить в виде чисел фиксированной разрядности.
- В общем случае нам хотелось бы найти алгоритм сортировки, который одновременно обладал бы высокой эффективностью, стабильностью, выполнением на месте и адаптивностью. Но, как и в других разделах алгоритмов и структур данных, не существует одного алгоритма сортировки, способного удовлетворить всем этим требованиям одновременно. На практике приходится выбирать подходящий алгоритм в зависимости от свойств данных.
- На рисунке 11-19 сравниваются эффективность, стабильность, выполнение на месте и адаптивность основных алгоритмов сортировки.

Рисунок 11-19 Сравнение алгоритмов сортировки

### 2. Вопросы и ответы

В: В каких случаях стабильность алгоритма сортировки является обязательной?

В реальных задачах нам может понадобиться сортировать объекты по некоторому атрибуту. Например, у студентов есть два атрибута: имя и рост. Мы хотим выполнить многоуровневую сортировку: сначала отсортировать по имени и получить `(A, 180) (B, 185) (C, 170) (D, 170)` , а затем отсортировать по росту. Если используемый алгоритм сортировки нестабилен, то мы можем получить `(D, 170) (C, 170) (A, 180) (B, 185)` .

Нетрудно увидеть, что в этом случае студенты D и C поменялись местами, порядок по имени разрушился, а именно этого мы и не хотим.

В: Можно ли поменять местами порядок «поиска справа налево» и «поиска слева направо» в разделении с опорным элементом?

Нет. Если в качестве опорного элемента выбирается самый левый элемент, необходимо сначала выполнять «поиск справа налево», а уже затем - «поиск слева направо». Этот вывод кажется немного неочевидным, поэтому разберем его подробнее.

Последний шаг `partition()` - это обмен `nums[left]` и `nums[i]` . После обмена все элементы слева от опорного должны быть `<=` опорного, а значит, перед этим обменом должно выполняться условие `nums[left] >= nums[i]`. Если сначала выполнять «поиск слева направо», то в случае, когда не удается найти элемент больше опорного, цикл завершится в состоянии `i == j` , и при этом может оказаться, что `nums[j] == nums[i] > nums[left]`. Иными словами, на последнем шаге обмена элемент, больший опорного, будет помещен в начало массива, из-за чего разделение завершится неверно.

Например, для массива `[0, 0, 0, 0, 1]` , если сначала выполнять «поиск слева направо», после разделения получится `[1, 0, 0, 0, 0]` , а это неправильный результат.

Если же выбрать `nums[right]` в качестве опорного элемента, то ситуация станет противоположной, и тогда сначала нужно выполнять «поиск слева направо».

В: Почему при оптимизации глубины рекурсии в быстрой сортировке выбор короткого массива гарантирует, что глубина рекурсии не превысит \(\log n\) ?

Глубина рекурсии - это число текущих рекурсивных вызовов, которые еще не завершились. На каждом раунде разделения исходный массив разбивается на два подмассива. После оптимизации глубины рекурсии длина подмассива, в который мы продолжаем рекурсивный спуск, не превышает половины длины исходного массива. Если рассматривать худший случай, когда длина каждый раз становится ровно вдвое меньше, итоговая глубина рекурсии и будет равна \(\log n\) .

В исходной версии быстрой сортировки может происходить последовательный рекурсивный вызов для более длинных массивов. В худшем случае это будут длины \(n\) , \(n - 1\) , \(\dots\) , \(2\) , \(1\) , а глубина рекурсии окажется равной \(n\) . Оптимизация глубины рекурсии как раз и позволяет избежать такого сценария.

В: Если все элементы массива равны, будет ли временная сложность быстрой сортировки равна \(O(n^2)\) ? Как справиться с таким вырождением?

Да. Для этого случая можно рассмотреть разделение массива на три части: элементы меньше опорного, равные опорному и большие опорного. Рекурсию нужно продолжать только для частей меньше и больше опорного. При таком подходе массив, целиком состоящий из одинаковых элементов, будет отсортирован всего за один раунд разделения.

В: Почему худшая временная сложность блочной сортировки равна \(O(n^2)\) ?

В худшем случае все элементы попадут в один и тот же блок. Если затем сортировать этот блок алгоритмом со сложностью \(O(n^2)\) , то общая временная сложность тоже станет \(O(n^2)\) .

##### Оставляйте свои идеи, вопросы и предложения в комментариях