Есть ли когда-нибудь веская причина использовать сортировку вставками?
Для сортировки общего назначения ответом будет "нет", так как быстрая сортировка, сортировка слиянием и сортировка кучи имеют тенденцию работать лучше в сценариях среднего и наихудшего случая. Однако сортировка вставкой, по-видимому, лучше всего подходит для инкрементальной сортировки, то есть добавления элементов в список по одному в течение продолжительного периода времени при сохранении сортировки списка, особенно если сортировка вставкой реализована как связанный список (O(log n) средний случай против O(n)). Тем не менее, куча, кажется, в состоянии выполнить только (или почти) также для инкрементальной сортировки (добавление или удаление отдельного элемента из кучи имеет худший вариант O(log n)). Итак, что именно может предложить сортировка вставками по сравнению с другими алгоритмами сортировки или кучами, основанными на сравнении?
7 ответов
С http://www.sorting-algorithms.com/insertion-sort:
Хотя это один из простейших алгоритмов сортировки с O (n2) временем наихудшего случая, сортировка вставкой является предпочтительным алгоритмом, когда данные почти сортируются (потому что они адаптивные) или когда размер проблемы мал (потому что он имеет низкие накладные расходы).
По этим причинам, а также потому, что он также стабилен, сортировка вставки часто используется в качестве рекурсивного базового случая (когда размер проблемы невелик) для алгоритмов сортировки "разделяй и властвуй" с более высокими издержками, таких как сортировка слиянием или быстрая сортировка.
Важной концепцией при анализе алгоритмов является асимптотический анализ. В случае двух алгоритмов с разными асимптотическими временами выполнения, таких как один O(n^2) и один O(nlogn), как в случае с сортировкой вставки и быстрой сортировкой соответственно, не определено, что один быстрее другого.
Важным отличием такого анализа является то, что для достаточно большого N один алгоритм будет быстрее другого. При анализе алгоритма вплоть до термина, такого как O(nlogn), вы отбрасываете константы. При реалистическом анализе работы алгоритма эти константы будут важны только для ситуаций с малым n.
Так что это значит? Это означает, что для некоторых малых n некоторые алгоритмы работают быстрее. Эта статья от EmbeddedGurus.net включает интересный взгляд на выбор различных алгоритмов сортировки в случае ограниченного пространства (16 КБ) и системы с ограниченной памятью. Конечно, статья ссылается только на сортировку списка из 20 целых чисел, поэтому большие порядки n не имеют значения. Более короткий код и меньшее потребление памяти (а также предотвращение рекурсии) были в конечном итоге более важными решениями.
Сортировка вставки имеет низкие накладные расходы, ее можно записать довольно кратко, и она имеет несколько двух ключевых преимуществ: она стабильна и имеет довольно быстрый работающий случай, когда ввод почти отсортирован.
Да, есть причина использовать сортировку вставки или один из ее вариантов.
Варианты сортировки (быстрая сортировка и т. Д.) Других ответов здесь предполагают, что данные уже находятся в памяти и готовы к отправке.
Но если вы пытаетесь прочитать большое количество данных из более медленного внешнего источника (например, с жесткого диска), большое количество времени будет потрачено впустую, поскольку узким местом является канал данных или сам диск. Это просто не может идти в ногу с процессором. Естественная серия ожиданий происходит во время любого чтения. Эти ожидания - потраченные впустую циклы процессора, если вы не используете их для сортировки по ходу дела.
Например, если вы должны были принять решение, это будет следующим:
- Прочитайте тонну данных в выделенном цикле в память
- Сортировать эти данные
Скорее всего, это займет больше времени, чем если бы вы делали следующее в двух потоках.
Тема А:
- Читать данные
- Поместить данные в очередь FIFO
- (Повторяйте, пока данные не будут исчерпаны с диска)
Нить Б:
- Получить данные из очереди FIFO
- Вставьте его в нужное место в вашем отсортированном списке
- (повторять до тех пор, пока очередь не станет пустой И поток А не скажет "сделано")
... вышеизложенное позволит вам использовать потраченное впустую время. Примечание. Тема B не препятствует выполнению темы A.
К тому времени, когда данные полностью прочитаны, они будут отсортированы и готовы к использованию.
Большинство процедур сортировки будет использовать быструю сортировку и затем сортировку вставкой для очень маленьких наборов данных.
Если вы говорите о сохранении отсортированного списка, нет никакого преимущества перед каким-то деревом, оно просто медленнее.
Ну, может быть, он потребляет меньше памяти или является более простой реализацией.
Вставка в отсортированный список будет включать сканирование, что означает, что каждая вставка имеет O(n), поэтому сортировка n элементов становится O(n^2)
Вставка в контейнер, такой как сбалансированное дерево, обычно это log(n), поэтому сортировка O(n log(n)), что, конечно, лучше.
Но для небольших списков это вряд ли имеет значение. Вы можете использовать сортировку вставки, если вам нужно написать ее самостоятельно без каких-либо библиотек, списки небольшие и / или вам не важна производительность.
ДА,
Сортировка вставок лучше, чем Быстрая сортировка в коротких списках.
На самом деле оптимальная быстрая сортировка имеет пороговое значение размера, на котором она останавливается, и затем весь массив сортируется путем сортировки вставкой сверх пороговых пределов.
Также...
Для поддержания табло сортировка бинарных вставок может быть настолько хороша, насколько это возможно.
Смотрите эту страницу.
Для небольших массивов сортировка вставки выполняется быстрее, чем быстрая сортировка. Java 7 и Java 8 используют двойную сводную сортировку для сортировки примитивных типов данных. Двойная поворотная быстрая сортировка выполняет типичную одинарную быструю сортировку. Согласно алгоритму двойной круговой быстрой сортировки:
- Для небольших массивов (длина < 27) используйте алгоритм сортировки вставками.
- Выберите два центра...........
Определенно, сортировка вставкой выполняет быструю сортировку для небольших массивов, поэтому вы переключаетесь на сортировку вставкой для массивов длиной менее 27. Причиной может быть отсутствие рекурсий в сортировке вставок.
Источник: http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf