HW3 Report — C

Language / toolchain

• Language: C (C11)
• Compiler: gcc (Ubuntu 15.2.0-16ubuntu1) 15.2.0, confirmed with gcc --version inside WSL2 Ubuntu.
• Build flags: -O2 -std=c11
• Build/run command:

  gcc -O2 -std=c11 -o quicksort quicksort.c
  ./quicksort
  

• Environment: WSL2 Ubuntu, AMD Ryzen 7 5800H (8 cores / 16 threads, ~3.2 GHz base), 32 GB RAM, Windows 11 Pro host.

Randomized pivot / RNG

Pivot selection follows CLRS's RANDOMIZED-PARTITION: at every partition call on subarray [lo, hi], an index r is drawn uniformly from [lo, hi] via r = lo + (rand() % (hi - lo + 1)), arr[r] is swapped with arr[hi], and then a standard Lomuto partition runs using arr[hi] as the pivot. RANDOMIZED-QUICKSORT then recurses on the two resulting subarrays.

RNG used: C standard library rand(), seeded once at program start with srand((unsigned int)time(NULL)). rand()'s quality is limited (e.g. glibc's implementation, while not the weakest possible, has known statistical imperfections and low periodicity guarantees compared to modern PRNGs such as PCG or Mersenne Twister, and low-order bits can be less random on some implementations). This is acceptable here per the assignment's allowance of rand()/<random> for C, and its statistical quality has no material effect on this experiment, which only needs a plausible uniformly-random pivot choice to avoid worst-case O(n^2) behavior on adversarial/sorted inputs — it is not being used for cryptographic or research-grade randomness.

External code

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

Results

Full results (also in results/c.csv):

Run stopped after 17 iterations because the elapsed time for n = 65,536,000 (5.586515 s) exceeded the 4.0 s cutoff. (25-iteration and 200,000,000-n caps were not reached.) Total wall-clock time for the whole program run (build excluded) was approximately 11.4 s.

Growth analysis

The observed timings are consistent with the expected O(n log n) average-case running time of randomized quicksort. Doubling n should roughly double the time and add a small extra factor proportional to 1/log n at each step (since T(2n)/T(n) ≈ 2·(log(2n)/log n) = 2·(1 + 1/log n)); for n in this run's range (log2 n from ~10 to ~26), that predicts a per-doubling ratio tapering from around 2.2 down toward roughly 2.05–2.1. The measured ratios match this closely once n is large enough to amortize fixed overhead: from n = 128,000 onward the per-doubling ratio stays in the ~1.9–2.2 range (e.g. 128,000→256,000 is 2.01x, 1,024,000→2,048,000 is 1.92x, 32,768,000→65,536,000 is 2.23x), tracking the expected n log n curve well. At small n (1,000–32,000) the ratios are noisier (as low as 1.68x, as high as 2.47x) because the absolute times are only tens to a few hundred microseconds, where timer resolution, memory-allocation cost, and one-off process/cache warmup effects are a larger fraction of the measurement — this is expected measurement noise rather than an algorithmic anomaly. No other anomalies (no GC pauses or JIT warmup apply to compiled C) were observed; recursion depth from randomized pivoting stayed well within stack limits for all tested n.