Отличие между алгоритмами сортировки

Question

Есть ли способ отличить алгоритмы сортировки от их исполняемых файлов? Я нашел эту проблему в списке рассылки для программирования varsity, который выглядит следующим образом: Скажем, у меня есть несколько исполняемых файлов, сортирующих массив данных с использованием разных алгоритмов. Я знаю, какие алгоритмы используются для кодирования этих исполняемых файлов, но я не знаю, какой алгоритм использовался в исполняемом файле. Алгоритмы, используемые являются:

1. неосведомленному BUBBLE СНП
2. BUBBLE SORT С НАЧАЛА ВЫХОДА
3. ТРАДИЦИОННАЯ INSERTION СНП
4. INSERTION СНП В СПИСОК
5. INSERTION СНП с двоичным ПОИСК
6. ТРАДИЦИОННАЯ ВЫБОР СНП
7. MERGE SORT
8. TRADITIONAL QUICK SORT
9. БЫСТРЫЙ СНП медиана ТРИ
10. рандомизированное БЫСТРОГО СНП
11. Шелла TIMES 4
12. BOGO СНП
13. RADIX СНП LSD ПЕРВЫЙ
14. ВЕДРО СНП
15. СЧЕТ СНП

Answer 1

You могут проверить их асимптотическое поведение, предоставив им больший и больший ввод, но многие из перечисленных алгоритмов попадают в одинаковые классы сложности, поэтому вы не сможете различать, скажем, сортировку слияния и быструю сортировку, основанную только на этом.

Чтобы разбить некоторые из этих вырождений, вы также можете посмотреть на использование памяти различных исполняемых файлов, чтобы продолжить сортировку слияния и быстрый пример сортировки, вы увидите, что для сортировки слияния потребуется дополнительное пространство O (n), а затем quick sort для выполнения сортировки потребуется только O (log n) дополнительное пространство (размер стека).

Возможно, вы сможете что-то вывести из-за того, что они дают вырожденный ввод, например, мегабайт нулей или мегабайт обратных строк, например. Но вы не смогли бы сделать больше, чем образованные догадки.

(Excellent комментарии ниже. Создание этого сообщества вики, не стесняйтесь редактировать.)

Answer 2

Изменить типы данных и объем данных ввода и сравнить время выполнения.

Изменение характера данных (повторение небольших чисел (несколько цифр), по сравнению с широко распространенными данными без дубликатов) помогает определить, основан ли алгоритм сортировки на основе сравнения (сортировка по принципу «radix/bucket» или «sort-based») , Например, сортировка 1000000 1-значных чисел является супер быстрой с сортировкой ведра, поскольку она масштабируется в основном за счет количества цифр, но медленнее для сортировочных сортировок, которые в основном не зависят от размера набора данных.

Вы также можете адаптировать данные, чтобы лучше выполнять некоторые алгоритмы над другими, например, использовать наилучший сценарий и худший сценарий для различных алгоритмов и искать EXE с наиболее значительным изменением времени выполнения.

Например, чтобы различать сортировку вставки и сортировку, используйте почти сортированный набор результатов, подобный (2, 3, ...98, 99, 1). Сортировка вставки будет делать один сдвиг вставки, а затем следующая проверка будет замечена, что список отсортирован. Это займет почти нет времени. Выбрать сортировку придется поменять на каждый индекс, так как минимум всегда будет в конечном индексе, и это займет много времени.

Answer 3

используйте следующую команду в CMD, вы найдете время обработки для каждого кода, с помощью которого мы можем их заказать. echo% time% filename.exe echo% time%