Algorithm Benchmarks

A collection of algorithm implementations, experiments, stress tests, and benchmarks.

The goal of this repository is to explore how algorithms behave in practice, not just in theory. Most experiments compare custom implementations against highly optimized standard library implementations while measuring runtime under different conditions.

Current Experiments

Sorting Algorithms

• Quicksort (First Element Pivot) vs std::sort

  • Custom implementation of Quicksort
  • Stress-tested against std::sort
  • Benchmarked with different compiler optimization levels (-O2, -O3)
  • Future plans:
    • Randomized Pivot Quicksort
    • Median-of-Three Quicksort
    • Merge Sort
    • Heap Sort
    • Performance on sorted, reverse-sorted, and duplicate-heavy inputs

Range Queries

• Sparse Table (Range Minimum Query)

  • Implementation of a Sparse Table for $O(1)$ query time after $O(n \log n)$ preprocessing.
  • Performance Analysis: Observed massive speedups (up to 410x) over naive $O(n)$ queries.
  • Log Table Optimization: Compared log2() calls against precomputed log tables; observed $\sim 1.28\text{x}$ improvement under -O3 optimization.
  • Scale Testing: Conducted large-scale stress tests with $\sim 250\text{M}$ elements and $\sim 256\text{M}$ queries, noting that table construction dominates the total runtime at extreme scales.
  • Verification: Used a custom hashing mechanism to validate correctness across massive datasets while minimizing memory overhead.

Repository Structure

.
├── quicksort_vs_std_sort/
│   ├── README.md
│   ├── quicksort_first_element.cpp
│   ├── test_generator.cpp
│
├── sparse_tables/
│   ├── sparse_min.cpp
│   └── sparse_min_log_test.cpp
│
└── clock.cpp

Notes

• All benchmarks are performed on the same generated input wherever possible.
• Results are intended for learning and exploration rather than rigorous scientific benchmarking.
• Every implementation is stress-tested against a trusted reference implementation before benchmarking.

Utilities

clock.cpp

Contains examples and references for timing code using the C++ chrono library.