Блум
Мыслитель
(8721)
1 день назад
Метод пузырька не является самым быстрым при сортировке, но для небольших наборов данных он обычно работает быстрее, чем более сложные алгоритмы.
Это связано с тем, что для каждой итерации простые алгоритмы выполняют меньше вычислений, чем сложные.
Андрей
Высший разум
(464982)
1 день назад
Пузырьковая сортировка никак не является "самым быстрым" алгоритмом. Наоборот, наивные сортировки (пузырёк, выбор, вставка) являются очень медленными и неприменимы для больших объёмов данных.
Наивные сортировки отличаются тем, что кол-во производимых действий (сравнений и перестановок) пропорционально квадрату длины массива. Увеличив длину массива в 10 раз, получим увеличение кол-ва выполняемых действий (и, следовательно, время работы) в 100 раз.
Тогда как при использовании быстрых сортировок при увеличении длины массива в 10 раз кол-во действий увеличится лишь в 10 * log(10) раз. И чем длиннее сортируемый массив, тем больше разница в количестве выполняемых действий между быстрой и наивной сортировкой.
Но уменьшение кол-ва действий в быстрых сортировках достигается тем, что каждое действие становится сложнее и медленнее, чем в наивных сортировках. Мы выполняем меньшее кол-во более медленных действий. Потому, на крошечных массивах, когда разница в кол-ве действий между быстрой и наивной сортировками невелика, быстрее будет работать именно наивная сортировка, производящая чуть больше более быстрых действий.
Jurijus Zaksas
Искусственный Интеллект
(449365)
1 день назад
Ничто.
В общем случае быстрее всего работает QuickSort - рекуррентный метод сортировки, достаточно сложный в реализации. Ничего лучше пока не придумали.
Лучше только параллельный QuickSort, но сие не совсем честно :)
ПапаВысший разум (144958)
1 день назад
Да ладно, не придумали. Я на литкоде радиксом рву всех этих индусов с их квиксортами и тимсортами. Спецом именно этот участком замерял - выигрыш в разы даже на малых массивах (1000 и менее), а уж на больших - все квиксорты вместе с индусами отдыхают.