Почему сортировка Insertion лучше, чем Quick sort для небольшого списка элементов?

Ответ 1

Нотация Big-O описывает ограничивающее поведение, когда n большое, также известное как асимптотическое поведение. Это приближение. (См. Http://en.wikipedia.org/wiki/Big_O_notation)

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

Этот вопрос описывает некоторые дополнительные преимущества сортировки вставками. (Есть ли веская причина использовать сортировку вставками?)

Ответ 2

Определите "маленький".

При сравнении алгоритмов сортировки я узнал, что переход от быстрой сортировки к сортировке вставки - несмотря на то, что говорили все, - на самом деле вредит производительности (рекурсивная quicksort в C) для массивов размером более 4 элементов. И эти массивы могут быть отсортированы с помощью оптимального алгоритма сортировки по размеру.

При этом всегда помните, что O(n...) - это только количество сравнений (в данном конкретном случае), а не скорость алгоритма. Скорость зависит от реализации, e. g., если ваша quicksort функционирует как или не рекурсивная и как быстро выполняются вызовы функций.

И последнее, но не менее важное: большая нотация - это только верхняя граница.

Если для алгоритма A требуются 10000 n log n сравнения, а для алгоритма B требуется 10 n ^ 2, первая - O(n log n), а вторая - O(n ^ 2). Тем не менее, второй, вероятно, будет быстрее.

Ответ 3

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

Это важно, потому что постоянные факторы и накладные расходы могут сильно различаться между процессорами и между реализациями: производительность, которую вы получаете для однопоточной Базовой программы на машине 6502, будет сильно отличаться от того же алгоритма, реализованного как программа C, работающая на процессор Intel i7. Обратите внимание, что оптимизация реализации также является фактором: внимание к деталям часто может дать вам значительное повышение производительности, даже если все остальные факторы одинаковы!

Однако постоянный фактор и накладные расходы по-прежнему важны. Если ваше приложение гарантирует, что N никогда не становится очень большим, асимптотическое поведение O (N ^ 2) по сравнению с O (N log N) не вступает в игру.

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

Ответ 4

Это вопрос о константах, которые привязаны к времени выполнения, которое мы игнорируем в примечании большой о (потому что нас интересует порядок роста). Для сортировки вставки время работы равно O (n ^ 2), т.е. T (n) <= c (n ^ 2), тогда как для Quicksort это T (n) <= k (nlgn). Поскольку c довольно мало, для малых n время выполнения сортировки вставки меньше, чем у Quicksort.....

Надеюсь, что это поможет...

Ответ 5

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

Ответ 6

Хорошим реальным примером, когда сортировка вставкой может использоваться вместе с быстрой сортировкой, является реализация функции qsort из glibc.

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

Краткое описание текущей реализации из исходного кода (вы найдете много полезной информации в комментариях, если посмотрите на нее):

1. Нерекурсивна

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

3. Только быстро сортирует разделы TOTAL_ELEMS/MAX_THRESH, оставляя вставку сортировки, чтобы упорядочить элементы MAX_THRESH в каждом разделе. Это большой выигрыш, поскольку сортировка вставкой выполняется быстрее для небольших, в основном отсортированных сегментов массива.

4. Больший из двух подразделов всегда помещается в стек первым

Что означает значение MAX_THRESH? Ну, просто небольшое постоянное магическое значение, которое

был выбран для лучшей работы на Sun 4/260.