Есть ли веская причина использовать Insertion Sort?

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

Ответ 1

Из http://www.sorting-algorithms.com/insertion-sort:

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

Прочитайте тонну данных в выделенном цикле в памяти
Сортировка данных

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

Тема А:

Прочитать исходную информацию
Установите дату в очередь FIFO
(Повторяйте до тех пор, пока данные не будут исчерпаны с диска)

Тема B:

Получить нулевую точку из очереди FIFO
Вставьте его в нужное место в отсортированном списке
(повторять до тех пор, пока очередь не будет пустой И Thread A говорит "done" ).

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

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

Ответ 4

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

Ответ 5

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

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

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

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

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

Ответ 6

ДА,

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

Фактически оптимальный Quick Sort имеет порог размера, на который он останавливается, а затем весь массив сортируется путем сортировки вставки по пороговым значениям.

Также...

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

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

Ответ 7

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

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

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

Ответ 8

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

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

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

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