Алгоритм представляет собой гибрид поразрядной сортировки MSD и быстрой сортировки строк: когда размер сортируемого подмассива меньше некоторого порога, он сортируется с помощью варианта быстрой сортировки, оптимизированного для строк, а не с помощью поразрядной сортировки.
Вот полученный график:
Здесь, по оси x — размеры входных массивов, на оси y — среднее количество сравнений, выполненных среди 50 случайно сгенерированных массивов соответствующего размера. Массивы содержат случайные строки длиной 10-200 символов (длина также случайна). Выбранное значение порога — 50. Локальный максимум — при размере ввода около 3000.
Вот результаты для порога = 25:
Шаблон тот же, хотя локальный максимум составляет 1500.
Похоже, что закономерность следующая: при относительно небольших размерах массивов количество сравнений достигает максимума при определенном размере, тогда как при больших входных данных количество сравнений достигает максимума. повышается. Последнее вполне естественно, но поведение на меньших массивах довольно неясно.
Поскольку поразрядная сортировка не является алгоритмом сортировки на основе сравнения, все сравнения выполняются с помощью быстрой сортировки. Похоже, что с массивами определенных размеров при быстрой сортировке приходится иметь дело с массивами наихудшего случая (теми, которые делают его O(n^2)) чаще, чем обычно. Почему это происходит?
Мой код:
Здесь индекс — это функция, которая принимает символ и возвращает его индекс в массиве. разрешенных символов. Он соблюдает порядок в таблице ascii, а индекс '\0' также равен 0. Можно считать, что его поведение аналогично приведению char к int.
Код: Выделить всё
struct RadixSortStep {
size_t l;
size_t r;
size_t c;
};
void radix_sort(std::vector &arr, CompCounter &cmp, bool sw) {
std::queue qs[allowed.size() + 1];
std::queue trace{};
trace.push({0, arr.size() - 1, 0});
while (!trace.empty()) {
auto [l, r, c] = trace.front();
trace.pop();
if (l >= r) {
continue;
}
if (sw && r - l
Подробнее здесь: [url]https://stackoverflow.com/questions/78448308/wierd-pattern-of-hybrid-radixquick-sort[/url]