Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Что заставляет метод пузырька быть самым быстрым при сортировке?

ФермаКактусов Высший разум (215162), открыт 1 день назад
5 ответов
Николай Горелов Знаток (427) 1 день назад
Потому что я ему так сказал
Блум Мыслитель (8721) 1 день назад
Метод пузырька не является самым быстрым при сортировке, но для небольших наборов данных он обычно работает быстрее, чем более сложные алгоритмы.
Это связано с тем, что для каждой итерации простые алгоритмы выполняют меньше вычислений, чем сложные.
Андрей Высший разум (464982) 1 день назад
Пузырьковая сортировка никак не является "самым быстрым" алгоритмом. Наоборот, наивные сортировки (пузырёк, выбор, вставка) являются очень медленными и неприменимы для больших объёмов данных.

Наивные сортировки отличаются тем, что кол-во производимых действий (сравнений и перестановок) пропорционально квадрату длины массива. Увеличив длину массива в 10 раз, получим увеличение кол-ва выполняемых действий (и, следовательно, время работы) в 100 раз.

Тогда как при использовании быстрых сортировок при увеличении длины массива в 10 раз кол-во действий увеличится лишь в 10 * log(10) раз. И чем длиннее сортируемый массив, тем больше разница в количестве выполняемых действий между быстрой и наивной сортировкой.

Но уменьшение кол-ва действий в быстрых сортировках достигается тем, что каждое действие становится сложнее и медленнее, чем в наивных сортировках. Мы выполняем меньшее кол-во более медленных действий. Потому, на крошечных массивах, когда разница в кол-ве действий между быстрой и наивной сортировками невелика, быстрее будет работать именно наивная сортировка, производящая чуть больше более быстрых действий.
ПапаВысший разум (144958) 1 день назад
По-моему, он просто троллит.
Jurijus Zaksas Искусственный Интеллект (449365) 1 день назад
Ничто.
В общем случае быстрее всего работает QuickSort - рекуррентный метод сортировки, достаточно сложный в реализации. Ничего лучше пока не придумали.
Лучше только параллельный QuickSort, но сие не совсем честно :)
ПапаВысший разум (144958) 1 день назад
Да ладно, не придумали. Я на литкоде радиксом рву всех этих индусов с их квиксортами и тимсортами. Спецом именно этот участком замерял - выигрыш в разы даже на малых массивах (1000 и менее), а уж на больших - все квиксорты вместе с индусами отдыхают.
Похожие вопросы