Все сложности, которые вы указали, верны, однако они даны в обозначениях Big O , поэтому все аддитивные значения и константы опущены
Чтобы ответить на ваш вопрос, нам нужно сосредоточиться на подробном анализе этих двух алгоритмов. Этот анализ можно сделать вручную или найти во многих книгах. Я буду использовать результаты Кнута Искусство компьютерного программирования .
Среднее количество сравнений:
- Вид пузыря : 12( N2- NперN- ( γ+ ln2 - 1 ) N) + O ( N--√)
- Вид вставки : 14( N2- N) + N- HN
- Сортировка выбора : ( N+ 1 ) НN- 2 Н
Теперь, если вы построите эти функции, вы получите что-то вроде этого:
Как видите, пузырьковая сортировка значительно ухудшается с увеличением количества элементов, даже если оба метода сортировки имеют одинаковую асимптотическую сложность.
Этот анализ основан на предположении, что входные данные являются случайными - что может быть не всегда верно. Однако, прежде чем мы начнем сортировку, мы можем случайным образом переставить входную последовательность (используя любой метод), чтобы получить среднее значение.
Я пропустил анализ сложности времени, потому что он зависит от реализации, но можно использовать аналогичные методы.
Бартош Прзыбыльски
источник
Сама функция, например количество сравнений и / или обменов, может отличаться для двух алгоритмов с одинаковыми асимптотическими затратами, если они растут с одинаковой скоростью.
Таким образом, асимптотический предел дает хорошее представление о том, как растут затраты на алгоритм по сравнению с размером входных данных, но ничего не говорит об относительной производительности различных алгоритмов в одном наборе.
источник
Bubble sort использует больше времени подкачки, тогда как сортировка выбора избегает этого.
При использовании выбора сортировки это меняет
n
время не более. но при использовании пузырьковой сортировки, он почти переставляетсяn*(n-1)
. И, очевидно, время чтения меньше, чем время записи даже в памяти. Время сравнения и другое время выполнения можно игнорировать. Так что время обмена является критическим узким местом проблемы.источник