Странный шаблон гибридной системы счисления + быстрая сортировка ⇐ C++

[Anonymous]

Я делал домашнее задание по курсу алгоритмов, и речь шла об алгоритмах сортировки строк. Мне предстояло реализовать разные алгоритмы, подсчитать количество сравнений символов, нарисовать график и объяснить результаты. Результаты одного из этих алгоритмов меня действительно смущают.
Алгоритм представляет собой гибрид поразрядной сортировки MSD и быстрой сортировки строк: когда размер сортируемого подмассива меньше некоторого порога, он сортируется с помощью варианта быстрой сортировки, оптимизированного для строк, а не с помощью поразрядной сортировки.
Вот полученный график:


Здесь по оси x указаны размеры входных массивов, по < По оси em>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/weird-pattern-of-hybrid-radixquick-sort[/url]