Результаты тестирования

На диаграммах (рис. 24) изображены результаты сравнений поразрядной сортировки (линия В) и быстрой (линия А), причем использовалась функция sort() из библиотеки STL.

Рис. 24

Анализ диаграмм:

• short
  Благодаря малой разрядности и простоте внутренних циклов поразрядная перегнала быструю сортировку уже на 100 элементах.
• long
  При переходе к типу long произошло двукратное увеличение количества проходов RadixPass, поэтому худшая асимптотика быстрой сортировки показала себя лишь после 600 элементов, где она начала отставать.
• float
  По графику видно, что для этого типа поразрядная сортировка оказалась гораздо эффективнее, нежели для long. В чем дело, ведь размер одинаков - 4 байта? Оказывается, на типе float резко возрастает время работы быстрой сортировки. Возможно, это связано с тем, что процессор, прежде чем делать какие-либо операции, переводит его в double, а потом работает с этим типом, который в 2 раза больше по размеру. Так или иначе, быстрая сортировка стала работать в 2 раза медленнее, и поразрядная вышла вперед после 100 элементов.
• double
  График показан с десятикратным увеличением. Размер типа увеличился в 2 раза, поэтому для небольших n поразрядная сортировка, конечно, отстает, но перегоняет быструю на массивах из нескольких тысяч элементов. Небольшое преимущество RadixSort длится приблизительно до 16000 элементов, когда данные начинают вылезать за пределы кэша. Соответственно, начинает играть свою роль медленный непоследовательный доступ (с шагами по 8 байт) к основной памяти. В результате поразрядная сортировка снова выбивается вперед лишь после 500000 элементов.

В программах используются переопределения:

Под переменной size принимается количество элементов в массиве, а для обозначения индекса последнего элемента используется N. Очевидно, что size=N+1.