HW3 Report - C++

Language / Toolchain

• Language: C++ (C++17)
• Compiler: g++ (Ubuntu 15.2.0-16ubuntu1) 15.2.0, run inside WSL2 Ubuntu (distro Ubuntu, 26.04 "Resolute Raccoon")
• Build flags: g++ -O2 -std=c++17 -o quicksort quicksort.cpp
• Machine: AMD Ryzen 7 5800H (8 cores / 16 threads, ~3.2 GHz base), 32 GB RAM, Windows 11 Pro host, benchmark executed inside WSL2 Ubuntu.

Algorithm / RNG

Randomized Quicksort implemented in-place on a std::vector<int>, following CLRS's RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION pseudocode:

• At every partition call randomizedPartition(a, p, r), a pivot index is drawn uniformly at random from [p, r] using std::uniform_int_distribution<int>(p, r) driven by a single std::mt19937 engine seeded from std::random_device.
• The randomly chosen element is swapped into position r, and a standard Lomuto partition is then run around a[r].
• randomizedQuicksort recurses into the smaller of the two resulting partitions and loops (tail-iterates) on the larger one, keeping expected recursion depth O(log n).
• The same mt19937 engine (seeded once, from std::random_device) is also used by generateRandomArray to fill each test array with random integers in [0, 1,000,000).

No std::sort, std::qsort, or any other library sort routine is used anywhere in the implementation.

External code

No external code used - original implementation based on CLRS's RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION pseudocode (Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 5).

Timing harness

Implemented exactly per HW3/DESIGN.md: n starts at 1000, a fresh array of n random ints in [0, 1,000,000) is generated each iteration (generation not timed), only the call to randomizedQuicksort is timed using std::chrono::steady_clock, n doubles each iteration, and the loop stops when an iteration's elapsed time exceeds 4.0s, or 25 iterations have run, or the next n would exceed 200,000,000 - whichever comes first. Results are written to HW3/results/cpp.csv (header n,time_seconds) and printed to stdout as the run happens.

Results

The run stopped after 17 iterations (n = 65,536,000), triggered by the elapsed time for that iteration (5.4526 s) exceeding the 4.0 s cutoff.

Full raw data: HW3/results/cpp.csv.

Growth analysis

For O(n log n) behavior, doubling n should roughly double the time, scaled by the slowly-growing factor log(2n)/log(n), which is close to 1 for large n (e.g. log2(2n)/log2(n) ≈ 1.05 around n ≈ 32,000,000). The measured per-doubling ratios settle into the ~1.9x-2.15x range from around n = 64,000 onward (e.g. 0.0068878/0.0033741 ≈ 2.04, 1.1308/0.538163 ≈ 2.10, 2.3516/1.1308 ≈ 2.08), which matches the expected O(n log n) growth very well - a pure O(n) algorithm would show ratios pinned at ~2.0 with no upward drift, while the mild upward drift seen here (ratios creeping from ~2.0 toward ~2.1-2.3 as n grows) is consistent with the log n factor. The earliest iterations (n = 1,000 to n = 8,000) show a noisier, larger-than-2x ratio (e.g. 0.0001262/0.0000382 ≈ 3.3), which is expected first-call/timer-resolution noise rather than an algorithmic anomaly - std::chrono::steady_clock has finite resolution and at microsecond-scale runtimes, fixed overhead (function call setup, RNG object construction, cache effects) dominates the true n log n signal. No other anomalies (no GC pauses, no JIT warmup - none applicable to a compiled, non-GC'd C++ binary) were observed; the growth is smooth and monotonic from n = 16,000 up to the final measured point.