В каких ситуациях более медленные алгоритмы сортировки (пузырьковая сортировка, выборочная сортировка и т. Д.) Более полезны, чем более быстрые алгоритмы, такие как быстрая сортировка?

Question

Я только что написал эссе об эффективности и полезности различных алгоритмов сортировки. Я пришел к выводу, что сортировка слиянием и быстрая сортировка были намного лучше при сортировке полностью рандомизированных списков. Я просто хотел спросить, в каких ситуациях более медленные алгоритмы сортировки для этого сценария (пузырьковая сортировка и выборочная сортировка) были бы более полезными или такими же полезными, как быстрая сортировка и сортировка слиянием.

Answer 1

Рекурсия, связанная с быстрой сортировкой или слиянием, может быть дорогой, когда мы снимаем довольно много чисел (может быть меньше 100)

В этом случае сортировка вставкой работает намного лучше.

Дажестандартные реализации библиотек сортировки в Java используют сочетание быстрого слияния и сортировки с вставкой

HTH

Answer 2

Существуют стабильные алгоритмы сортировки, которые сохраняют элементы, которые сравниваются, в первоначальном порядке. Если это важно для вас, вы бы использовали алгоритм стабильной сортировки, даже если он медленнее.

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

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

Если вы знаете, что массив был отсортирован, а затем было изменено небольшое количество элементов, для этого есть умный алгоритм (который вы найдете где-то на cs.stackexchange.com): если k элементов былоизменено, вы можете извлечь не более 2 тыс. элементов в отдельный массив, отсортировать их (скорее всего, с помощью быстрой сортировки) и объединить два массива.

Если вы используете библиотечную функцию, вряд ли это будет простая быстрая сортировка. Например, реализация Apple ищет отсортированный диапазон в начале и в конце массива, и, если уже отсортировано значительное количество элементов, это дает преимущество (например, сортировка конкатенации двух отсортированных массивов выполняется за линейное время).

Answer 3

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

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