Есть ли когда-нибудь веская причина использовать сортировку вставками?

Question

Для сортировки общего назначения ответом будет "нет", так как быстрая сортировка, сортировка слиянием и сортировка кучи имеют тенденцию работать лучше в сценариях среднего и наихудшего случая. Однако сортировка вставкой, по-видимому, лучше всего подходит для инкрементальной сортировки, то есть добавления элементов в список по одному в течение длительного периода времени при сохранении сортировки списка, особенно если сортировка вставкой реализована как связанный список n) средний случай против O (n)). Тем не менее, куча, кажется, в состоянии выполнить только (или почти) также для инкрементальной сортировки (добавление или удаление отдельного элемента из кучи имеет худший вариант O (log n)). Итак, что именно может предложить сортировка вставками по сравнению с другими алгоритмами сортировки или кучами, основанными на сравнении?

Answer 1

С http://www.sorting -algorithms.com / insert-sort :

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

По этим причинам, а также потому, что он также стабилен, сортировка вставок часто используется в качестве рекурсивного базового случая (когда размер проблемы мал) для выше накладные расходы «разделяй и властвуй» алгоритмы сортировки, такие как сортировка слиянием или быстрая сортировка.

Answer 2

Важной концепцией при анализе алгоритмов является асимптотический анализ. В случае двух алгоритмов с разными асимптотическими временами выполнения, таких как один O (n ^ 2) и один O (nlogn), как в случае с сортировкой вставки и быстрой сортировкой соответственно, не определено, что один быстрее другой.

Важным отличием такого анализа является то, что для достаточно большого N один алгоритм будет быстрее другого. При анализе алгоритма до такого термина, как O (nlogn), вы отбрасываете константы. При реалистическом анализе работы алгоритма эти константы будут важны только для ситуаций с малым n.

Так что это значит? Это означает, что для некоторых малых п некоторые алгоритмы работают быстрее. Эта статья от EmbeddedGurus.net содержит интересную перспективу выбора различных алгоритмов сортировки в случае ограниченного пространства (16 КБ) и системы с ограниченной памятью. Конечно, статья ссылается только на сортировку списка из 20 целых чисел, поэтому большие порядки n не имеют значения. Более короткий код и меньшее потребление памяти (а также предотвращение рекурсии) были в конечном итоге более важными решениями.

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

Answer 3

Да, есть причина использовать сортировку вставки или один из ее вариантов.

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

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

Например, если вы решили принять следующее решение:

1. Считать тонну данных в выделенном цикле в память
2. Сортировать эти данные

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

Тема A:

1. Считать данные
2. Поместить данные в очередь FIFO
3. (повторять до тех пор, пока данные с диска не будут исчерпаны)

Резьба B:

1. Получить данные из очереди FIFO
2. Вставьте его в нужное место в вашем отсортированном списке
3. (повторять до тех пор, пока очередь не станет пустой И поток А не скажет "готово").

... вышеизложенное позволит вам использовать потраченное впустую время. Примечание. Тема B не препятствует выполнению темы A.

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

Answer 4

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

Answer 5

ДА,

Сортировка вставкой лучше, чем Быстрая сортировка в коротких списках.

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

Кроме того ...

Для ведения табло сортировка бинарных вставок может быть такой же хорошей, как и у нее.

См. эту страницу .

Answer 6

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

Ну, может, он потребляет меньше памяти или является более простой реализацией.

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

Вставка в контейнер, такой как сбалансированное дерево, обычно это log (n), поэтому сортировка O (n log (n)), что, конечно, лучше.

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

Answer 7

Для небольших массивов вставка сортировки выполняется быстрее, чем быстрая сортировка. Java 7 и Java 8 используют двойную сводную сортировку для сортировки примитивных типов данных. Двойная поворотная быстрая сортировка выполняет типичную одинарную быструю сортировку. По алгоритму двойной круговой быстрой сортировки:

1. Для небольших массивов (длина <27) используйте алгоритм сортировки вставок. </li>
2. Выберите два центра ...........

Определенно сортировка вставки выполняет быструю сортировку для небольших массивов, и поэтому вы переключаетесь на сортировку вставки для массивов длиной менее 27 . Причиной может быть отсутствие рекурсий в сортировке вставки.

Источник: http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf