Количество перестановок в быстрой сортировке и сортировке выбором
Реализовал алгоритмы сортировки выбором и быстрой сортировки. Результат при сортировке 3000 элементов:
Выбором:
Сравнений: 4498500
Перестановок: 2975
Быстрая:
Сравнений: 80496
Перестановок: 18027
Это нормально что при быстрой сортировке больше перестановок или я неправильно реализовал алгоритм?
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Да, нормально.
Сортировка выбором вообще делает наименьшее количество перестановок (изо всех сортировок, основанных на сравнениях и обменах) - не более n (меньше на число элементов, уже стоящих на своих местах, если реализация это учитывает)