Используются ли эти алгоритмы сортировки в реальном мире?Сортировка выбора или вставки полезна вне академической среды?
Или это просто базовый пример алгоритма сортировки с n^2 сложностью?
Может ли кто-нибудь привести пример его использования?
Сортировка вставки - один из самых быстрых алгоритмов сортировки для сортировки очень маленьких массивов.
На практике многие реализации quicksort/mergesort останавливаются, когда подмассивы сортируются ниже определенного порога, а затем сортировка сортировки используется для этих небольших массивов.
Сортировка по выбору редко используется на практике.
Вставка сортировки на самом деле довольно быстро для небольших размеров ввода, из-за небольших скрытых констант по своей сложности. До некоторой степени, сортировка вставки быстрее, чем сортировка слияния.
Таким образом, для многих популярных алгоритмов сортировки, когда размер массива становится очень маленьким, используется сортировка вставки.
Bottomline: Алгоритм А О (N) может быть быстрее на практике, чем O алгоритма (N * LogN) при достаточно малых размеров входов, вследствие скрытых констант.
Да, сортировка вставки широко используется в промышленных приложениях. В основном это связано с тем фактом, что несколько популярных стандартных библиотек C++, таких как libstdc++ и libc++, реализуют процедуру sort как комбинацию сортировки вставки и сортировки по глубине.
Идея заключается в том, что сортировка вставки работает очень быстро на почти отсортированных массивах, в то время как для простой реализации быстрого сортированного ввода приводит к наихудшему поведению. Поэтому комбинированный алгоритм сначала применяет алгоритм quicksort-like для частичной сортировки ввода, а затем завершается вызовом сортировки вставки.
libc++ Вставка сортировки также используется для сортировки по умолчанию, если размер ввода достаточно мал (но больше пяти элементов, так как размеры < = 5 обрабатываются как особые случаи).
HP/Microsoft std :: sort() is introsort, quicksort с параметром глубины, который переключается на heapsort, если глубина становится слишком глубокой.
HP/Microsoft std :: stable_sort() - это тип timsort. Он использует сортировку вставки для создания групп из 32 отсортированных элементов, а затем использует сортировку слияния снизу вверх для объединения групп.
На боковой ноте сортировка слияния сверху вниз не используется ни в одной общей библиотеке, о которой я знаю. Вместо этого общие версии библиотек для внутренних (памяти) и внешних (дисковых) слияний - это все варианты сортировки спуска вверх (например, timsort). Тем не менее в классе или в статьях веб-сайта вы видите больше примеров сортировки слияния сверху вниз, чем сортировка слияния вверх.
определить приложения «реального мира» – AADProgramming
Пример использования: эффективность обучения и алгоритмы сортировки для студентов-информатиков –
«Приложения реального мира», например, где люди его используют? В таком случае мы должны использовать его? Есть ли какое-либо программное обеспечение или какой-либо модуль, чтобы это использовать? –