Почему сортировка вставок лучше, чем быстрая сортировка для небольшого списка элементов?
Разве вставка не сортирует O(n^2) > Быстрая сортировка O(nlogn)... так что для малых n отношение не будет таким же?
5 ответов
Нотация Big-O описывает ограничивающее поведение, когда n большое, также известное как асимптотическое поведение. Это приближение. (См. http://en.wikipedia.org/wiki/Big_O_notation)
Сортировка вставкой быстрее для малых n, потому что быстрая сортировка требует дополнительных затрат от рекурсивных вызовов функций. Сортировка вставками также более стабильна, чем быстрая сортировка, и требует меньше памяти.
Этот вопрос описывает некоторые дополнительные преимущества сортировки вставками. ( Есть ли веская причина использовать сортировку вставками?)
Определите "маленький".
При тестировании алгоритмов сортировки я обнаружил, что переключение с быстрой сортировки на сортировку вставкой - несмотря на то, что все говорили - на самом деле снижает производительность (рекурсивная быстрая сортировка в C) для массивов размером более 4 элементов. И эти массивы могут быть отсортированы с помощью алгоритма оптимальной сортировки в зависимости от размера.
При этом всегда имейте в виду, что O(n...) только количество сравнений (в данном конкретном случае), а не скорость алгоритма. Скорость зависит от реализации, например, является ли ваша функция быстрой сортировки рекурсивной или нет, и насколько быстро обрабатываются вызовы функций.
И последнее, но не менее важное: большие обозначения ой - это только верхняя граница.
Если алгоритм A требует 10000 n log n сравнения и алгоритм B требует 10 n ^ 2во-первых O(n log n) а второй O(n ^ 2), Тем не менее, второе будет (вероятно) быстрее.
O()- нотация обычно используется для характеристики производительности при больших проблемах, при этом сознательно игнорируя постоянные факторы и добавочные смещения к производительности.
Это важно, потому что постоянные факторы и накладные расходы могут сильно различаться в зависимости от процессора и между реализациями: производительность, которую вы получаете для однопоточной программы Basic на компьютере 6502, будет сильно отличаться от того же алгоритма, который реализован в программе на C, работающей на Intel i7 Процессор Обратите внимание, что оптимизация реализации также является фактором: внимание к деталям часто может значительно повысить производительность, даже если все остальные факторы одинаковы!
Тем не менее, постоянный фактор и накладные расходы все еще важны. Если ваше приложение гарантирует, что N никогда не становится очень большим, асимптотическое поведение O(N^2) против O(N log N) не вступает в игру.
Сортировка вставок проста, и для небольших списков она обычно быстрее, чем сравнительно реализованная быстрая сортировка или сортировка слиянием. Вот почему практическая реализация сортировки, как правило, прибегает к чему-то вроде вставки для "базового случая", вместо того, чтобы возвращаться к отдельным элементам.
Речь идет о константах, привязанных к времени выполнения, которые мы игнорируем в нотации big-oh (потому что нас интересует порядок роста). Для сортировки вставкой время выполнения равно O(n^2), т.е. T(n)<=c(n^2), тогда как для быстрой сортировки это T(n)<=k(nlgn). Поскольку c довольно мало, при малых n время выполнения сортировки вставки меньше, чем у Quicksort.....
Надеюсь, поможет...
Хорошим реальным примером, когда сортировка вставкой может использоваться в сочетании с быстрой сортировкой, является реализация qsort функция от glibc,
Первое, на что нужно указать qsort реализует алгоритм быстрой сортировки со стеком, поскольку он потребляет меньше памяти, стек реализуется с помощью директив макросов.
Краткое описание текущей реализации из исходного кода (вы найдете много полезной информации в комментариях, если посмотрите на нее):
Нерекурсивна
Выберите элемент сводки, используя дерево решений медиана-три
Только быстро сортирует разделы TOTAL_ELEMS / MAX_THRESH, оставляя сортировку вставки, чтобы упорядочить элементы MAX_THRESH в каждом разделе. Это большой выигрыш, поскольку сортировка вставкой выполняется быстрее для небольших, в основном отсортированных сегментов массива.
Больший из двух подразделов всегда помещается в стек первым
Что означает значение MAX_THRESH? Ну, просто небольшое постоянное магическое значение, которое
был выбран для работы лучше всего на Sun 4/260.
Как насчет бинарной сортировки? Вы можете абсолютно найти позицию для обмена, используя бинарный поиск.