Где я могу найти несколько важных тестов алгоритмов сортировки? - PullRequest
Новая
       37

Где я могу найти несколько важных тестов алгоритмов сортировки?

3 голосов
/ 21 января 2012

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

В идеале я хотел бы найти:

  • большой набор тестов сортировкикоторые ЗНАЧИТЕЛЬНО предоставляют мне эффективность моего алгоритма
  • большой набор уже существующих и сильно оптимизированных алгоритмов сортировки (с их кодом - независимо от языка)
  • еще лучше, программное обеспечениеэто обеспечивает адекватную среду для разработчиков алгоритмов сортировки

Вот пост, который я обнаружил ранее, который содержит 2 таблицы со сравнениями между timsort, quicksort, quivort с двойной сводкой и сортировкой Java 6: http://blog.quibb.org/2009/10/sorting-algorithm-shootout/В этих таблицах я вижу, что эти файлы TXT (начиная с 1245.repeat.1000.txt и заканчивая sequential.10000000.txt) содержат тестовые случаи для этих алгоритмов, но я нигде не могу найти исходные TXT!

Может ли кто-нибудь указать мне на любую ссылку со многими сортировочными тестами И / ИЛИ many ВЫСОКОЭФФЕКТИВНЫЕ алгоритмы сортировки?(это тесты, которые меня интересуют больше всего, алгоритмы сортировки есть по всему интернету)

Заранее большое спасибо!

1 Ответ

1 голос
/ 06 февраля 2012

Несколько вещей:

  • Быстрая сортировка сводит с ума рассортированные списки вперед и назад, поэтому ей потребуются другие типы списков.
  • Тестирование на случайных данных - это хорошо, но если вы хотите сравнить производительность различных алгоритмов, это означает, что вы не можете генерировать новые случайные данные каждый раз, иначе ваши результаты не будут надежными. Я думаю, что вы должны попытаться придумать псевдослучайный алгоритм, который записывает данные в порядке, основанном на количестве записей. Таким образом, данные, генерируемые для списков размером n, 10n и 100n, будут похожими.
  • Тестирование сортировки в первую очередь касается не скорости (до тех пор, пока алгоритм не будет завершен), а отношения сравнения к записям. Если для одной сортировки требуется 15 сравнений на одну запись в списке и еще 12 для одного и того же списка, вторая будет более эффективной, даже если она выполняется дважды. Для более тривиальных концепций сортировки в игру вступит также необходимое количество обменов.
  • Для тестирования используйте вектор целых чисел в оперативной памяти. Если алгоритм работает хорошо, вектор целых чисел может быть преобразован в вектор индексов в буфер, содержащий данные для сравнения. Такой алгоритм будет сортировать вектор значений на основе данных, на которые они указывают.
...