String Sort Algorithms Comparison

Сравнение обобщённых (QuickSort, MergeSort) и строково-специализированных (StringQuickSort, StringMergeSort, MSD Radix Sort) алгоритмов сортировки строк — по времени и числу посимвольных сравнений на разных типах входных данных: random, reverse, almost sorted, common prefix.

Как устроено

• StringGenerator — генерирует тестовые наборы строк (вихрь Мерсена)
• StringSortTester — прогоняет каждый алгоритм 7 раз, отбрасывает min/max и усредняет, считает сравнения и время, пишет CSV в results/sorting_benchmark.csv

Как запустить

Исследование — это два последовательных шага: сначала C++ считает и пишет сырые данные в results/sorting_benchmark.csv, потом Python читает этот CSV и строит графики в results/plots/.

# 1. Собрать и прогнать бенчмарк (C++) — пишет results/sorting_benchmark.csv
cmake -S . -B build && cmake --build build
./build/benchmark

# 2. Построить графики по CSV (Python) — читает results/sorting_benchmark.csv
pip install -r requirements.txt && python3 scripts/plot_builder.py

Результаты

Время выполнения

Количество сравнений

Усреднено по 7 запускам с отбросом min/max.

Выводы

• Строковые сортировки делают в 5–10 раз меньше сравнений, чем классические QuickSort/MergeSort ($O(n \log n)$ сравнений строк целиком против $O(n \log n)$ сравнений отдельных символов) — разница растёт с $n$.
• Сильнее всего это видно на Common Prefix: классические сортировки сравнивают строки целиком и «застревают» в общем префиксе длины $k$, то есть каждое сравнение стоит $O(k)$ вместо $O(1)$.
• MsdRadixSortWithQuickSort — самый быстрый: линейная сложность по данным $O(n \cdot w)$, где $w$ — длина строки, плюс переход на QuickSort на маленьких подотрезках.
• Almost Sorted почти не отличается от Random — перемешивается только половина элементов.