C: Анализ методов сортировки

Question

У меня есть множество различных алгоритмов сортировки, каждый из которых имеет следующую подпись:

void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH);

Существуют ли какие-либо тестовые наборы для сортировки, которые я мог бы использовать для целей эмпирического сравнения?

Answer 1

Это подробное обсуждение , а также ссылки на большое количество связанных веб-страниц, которые вы, вероятно, найдете полезными, также описывает полезный набор входных данных для тестирования алгоритмов сортировки (см. Связанную страницу для причины). Подводя итог:

1. Полностью случайным образом перетасованный массив
2. Уже отсортированный массив
3. Уже отсортировано в массиве в обратном порядке
4. Массив бензопил
5. Массив идентичных элементов
6. Уже отсортированный массив с N перестановками (с N от 0,1 до 10% размера)
7. Уже отсортированный массив в массиве в обратном порядке с N перестановками
8. Данные, которые имеют нормальное распределение с дублирующимися (или закрытыми) ключами (только для стабильной сортировки)
9. Псевдослучайные данные (дневные значения S & P500 или других индексов за десятилетие могут быть хорошим тестом; они доступны на Yahoo.com)

Answer 2

Окончательное исследование сортировки - Боб Седжвик докторская диссертация. Но в его учебниках по алгоритмам есть много полезной информации, и это первые два места, где я бы искал набор тестов и методологию. Если у вас был недавний курс, вы будете знать больше, чем я; В прошлый раз, когда у меня был курс, лучший метод состоял в том, чтобы использовать быструю сортировку по разделам размером 12, а затем выполнить сортировку вставки по всему массиву. Но ответы меняются так же быстро, как и оборудование.

В книгах Джона Бентли по программированию на Perls есть и другая информация о сортировке.

Вы можете быстро создать набор тестов, содержащий

• Случайные целые числа

• Сортированные целые числа

• Обратно отсортированные целые числа

• Сортированные целые числа, слегка возмущенные

Если память служит, это наиболее важные случаи для алгоритма сортировки.

Если вы хотите отсортировать массивы, которые не помещаются в кеш, вам нужно измерить эффекты кеша. valgrind действует, если медленно.

Answer 3

sortperf.py имеет хорошо подобранный набор тестовых примеров и использовался для поддержки эссе, найденного здесь здесь , и для того, чтобы сделать сортировку timsort в Python lo много лет назад. Обратите внимание, что, наконец, Java может перейти и на timsort, благодаря Джошу Блоку (см. здесь ), поэтому я думаю, что они написали свою собственную версию тестовых примеров - однако я могу не легко найти ссылку на него. (timsort, стабильный, адаптивный, итеративный вариант естественного слияния, особенно подходит для языков с семантикой ссылки на объект, таких как Python и Java, где «перемещение данных» является относительно дешевым [[поскольку все, что когда-либо перемещалось, это ссылки, называемые указателями) не капли неограниченного размера ;-)]], но сравнение может быть относительно дорогостоящим [[поскольку верхняя граница сложности функции сравнения не существует - но тогда это справедливо для любого языка, где сортировка может быть настроена с помощью пользовательского функция сравнения или извлечения ключа]]).

Answer 4

На этом сайте показаны различные алгоритмы сортировки с использованием четырех групп: http://www.sorting -algorithms.com /

В дополнение к четырем группам в ответе Нормана вы хотите проверить алгоритмы сортировки с набором чисел, которые имеют несколько сходств в числах:

• Все целые числа уникальны
• Одинаковое целое число во всей коллекции
• Несколько уникальных ключей

Изменение количества элементов в коллекции также является хорошей практикой, проверяя каждый алгоритм с помощью 1K, 1M, 1G и т. Д., Чтобы увидеть, каковы значения памяти для этого алгоритма.