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

Question

Разве не вставка сортировки O (n ^ 2)> Быстрая сортировка O (nlogn) ... так что для малых n отношение не будет таким же?

Answer 1

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

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

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

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

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

1. нерекурсивный

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

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

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

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

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

Answer 6

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