0

Реализовал алгоритмы сортировки выбором и быстрой сортировки. Результат при сортировке 3000 элементов:

Выбором:

Сравнений: 4498500
Перестановок: 2975

Быстрая:

Сравнений: 80496
Перестановок: 18027

Это нормально что при быстрой сортировке больше перестановок или я неправильно реализовал алгоритм?

1 ответ 1

0

Да, нормально.

Сортировка выбором вообще делает наименьшее количество перестановок (изо всех сортировок, основанных на сравнениях и обменах) - не более n (меньше на число элементов, уже стоящих на своих местах, если реализация это учитывает)

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.