Каковы критерии выбора алгоритма сортировки?

Question

Я читал метод сортировки, который включает в себя сортировку по пузырькам, сортировку по выбору, сортировку по слиянию, сортировку по куче, сортировку по контейнерам и т. Д. Они также содержат сложность по времени, которая помогает нам узнать, какая сортировка эффективна.Итак, у меня возник основной вопрос.Если мы будем содержать данные, то как мы будем выбирать сортировку.Временная сложность является одним из параметров, который помогает нам выбрать метод сортировки.Но у нас есть другой параметр, чтобы выбрать метод сортировки?

Где мы используем сортировку кучи?

Что является большим преимуществом сортировки кучи (кроме сложности времени O (n log n))?

В чем недостаток сортировки кучи?

Что такое время сборки для кучи?(Я слышал O (n), но я не уверен.)

Любой сценарий, в котором мы должны использовать сортировку кучи или сортировку кучи, является лучшим вариантом (кроме очереди с приоритетами)?

Перед тем, как применить к данным сортировку кучи, какой параметр мы рассмотрим в данных?

Answer 1

Двумя основными теоретическими особенностями алгоритмов сортировки являются временная сложность и пространственная сложность.

Как правило, сложность времени позволяет нам узнать, как изменяется производительность алгоритма при увеличении размера набора данных. Что нужно учитывать:

• Сколько данных вы ожидаете отсортировать? Это поможет вам узнать, нужно ли вам искать алгоритм с очень низкой временной сложностью.
• Насколько отсортированными будут ваши данные? Будут ли они частично отсортированы? Случайно отсортировано? Это может повлиять на временную сложность алгоритма сортировки. Большинство алгоритмов будут иметь худшие и лучшие случаи - вы хотите убедиться, что вы не используете алгоритм для набора данных наихудшего случая.
• Сложность времени не совпадает со временем выполнения. Помните, что сложность времени описывает только то, как производительность алгоритма меняется с увеличением размера набора данных. Алгоритм, который всегда делает один проход по всем входным данным, будет O (n) - его производительность линейно коррелирует с размером входного сигнала. Но алгоритм, который всегда делает два прохода над набором данных, также является O (n) - корреляция все еще линейна, даже если константа (и фактическое время выполнения) различна.

Аналогично, сложность пространства описывает, сколько места необходимо запустить алгоритму. Например, простой сортировке, такой как сортировка вставок , требуется дополнительный фиксированный объем пространства для хранения значения вставляемого элемента. Это сложность вспомогательного пространства O (1) - она ​​не изменяется в зависимости от размера ввода. Однако сортировка слиянием создает дополнительные массивы в памяти во время работы со сложностью вспомогательного пространства O (n). Это означает, что количество необходимого дополнительного пространства линейно коррелирует с размером ввода.

Конечно, разработка алгоритмов часто является компромиссом между временем и пространством - алгоритмы с малой пространственной сложностью могут требовать больше времени, а алгоритмы с малой временной сложностью могут требовать больше места.

Для получения дополнительной информации вы можете найти этот урок полезным.

---

Чтобы ответить на ваш обновленный вопрос, вам может пригодиться страница википедии по Сортировка кучи .

Answer 2

Если вы имеете в виду критерии для выбора типа сортировки, вот некоторые другие пункты для рассмотрения.

Количество данных, которое у вас есть: у вас есть десять, сто, тысяча или миллионы предметов для сортировки.

Сложность алгоритма: чем сложнее, тем больше тестов нужно будет провести, чтобы убедиться в его правильности.В небольших количествах пузырьковую или быструю сортировку легко кодировать и тестировать, в отличие от других сортировок, которые могут оказаться излишними для объема данных, которые вы должны отсортировать.

Сколько времени потребуется для сортировки: Еслиу вас большой набор, пузырьковая / быстрая сортировка займет много времени, но если у вас много времени, это может не быть проблемой.Однако использование более сложного алгоритма сократит время на сортировку, но за счет больших усилий при кодировании и тестировании, что может стоить того, если сортировка идет от длинного (часы / дни) до более короткого промежутка времени.

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

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