Полезны ли сортировки по выбору или вставке за пределами академической среды?

Есть ли у этих алгоритмов сортировки какое-либо применение в реальных приложениях?

Или это просто базовый пример алгоритма сортировки со сложностью n ^ 2?

Кто-нибудь может привести пример его использования?


sorting algorithm selection-sort insertion-sort
person Pranay Deep    schedule 05.02.2016    source источник
comment
определять приложения реального мира   -  person AADProgramming    schedule 05.02.2016
comment
Пример его использования: обучение эффективности и алгоритмов сортировки студентов, изучающих информатику.   -  person OneCricketeer    schedule 05.02.2016
comment
приложения реального мира, например, где люди его используют? В каком случае мы должны его использовать? Есть ли какое-либо программное обеспечение или какой-либо модуль для использования этого?   -  person Pranay Deep    schedule 05.02.2016
comment
@ cricket_007, мы это знаем. Вот почему я задаю этот вопрос. Спасибо за ответ.   -  person Pranay Deep    schedule 05.02.2016
comment
@Vhortex и cricket_007: если тебе все равно, ничего страшного. Вопрос правильный, и если вы не задумывались, ничего страшного.   -  person Aravind    schedule 05.02.2016
comment
@Aravind все равно? Какая часть моего комментария неверна. Все будет похоронено под библиотеку DLL. когда вы в последний раз просили конечного пользователя скомпилировать свой собственный алгоритм сортировки при использовании, например, excel. Вы когда-нибудь говорили Бобу, что он машинист для BOB, откройте свой компилятор и перейдите к строке 172, запустите проверку орфографии с 5 параметрами и загрузите ABC.DLL, пока вы в ней?   -  person Vhortex    schedule 05.02.2016
comment
@Aravind вопрос: есть ли у этих алгоритмов сортировки какое-либо применение в реальных приложениях ?. Не что это за алгоритмы сортировки.   -  person Vhortex    schedule 05.02.2016
comment
@Vhortex: Согласен, но любопытство никому не повредит. И они используются в реализациях, потому что они быстрые для небольших входов, вот в чем суть.   -  person Aravind    schedule 05.02.2016
comment
Опять же, вопрос в том, может ли он увидеть это в реальном мире, правда в том, что вы этого не сделаете. он будет скрыт и заменен более качественной реализацией. Это не будет выглядеть так, как есть. Так, как это разработал Academic.   -  person Vhortex    schedule 05.02.2016

Ответы (4)


arrow_upward
3
arrow_downward

Сортировка вставкой - один из самых быстрых алгоритмов сортировки очень маленьких массивов.

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

Выборочная сортировка на практике используется редко.

person Yu Hao    schedule 05.02.2016

arrow_upward
1
arrow_downward

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

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

Итог: алгоритм O (N 2) на практике может быть быстрее, чем алгоритм O (N * logN) для входов достаточно малого размера из-за скрытых констант.

person Aravind    schedule 05.02.2016

arrow_upward
1
arrow_downward

Да, сортировка вставками широко используется в промышленных приложениях. В основном это связано с тем, что несколько популярных стандартных библиотек C ++, таких как libstdc ++ и реализация libc ++ sort процедура как комбинация сортировки вставкой и быстрой сортировки с ограничением глубины.

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

В libc ++ сортировка вставки также используется для сортировки по умолчанию, если размер ввода достаточно мал (но больше пяти элементов, поскольку размеры ‹= 5 обрабатываются как особые случаи).

person kfx    schedule 05.02.2016

arrow_upward
0
arrow_downward

HP / Microsoft std :: sort () - это интросорт, быстрая сортировка с параметром глубины, который переключается на heapsort если глубина становится слишком глубокой.

HP / Microsoft std :: stable_sort () - это разновидность timsort. Он использует сортировку вставкой для создания групп из 32 отсортированных элементов, а затем использует сортировку слиянием снизу вверх для объединения групп.

Кстати, сортировка слияния сверху вниз не используется ни в одной известной мне известной библиотеке. Вместо этого общие версии библиотек для внутренней (память) и внешней (диск) сортировки слияния представляют собой разновидности сортировки слиянием снизу вверх (например, timsort). Тем не менее, в классе или в статьях на веб-сайтах вы видите больше примеров сортировки слиянием сверху вниз, чем сортировки слияния снизу вверх.

person rcgldr    schedule 05.02.2016