Quadratic Sorting Algorithms lab report

1. Title and aim

Comparative Analysis of Quadratic Sorting Algorithms: Bubble, Selection, and Insertion Sort. Measure the empirical operation counts (key comparisons and element swaps) of Bubble Sort, Selection Sort, and Insertion Sort across datasets of size n from 10 to 70 elements, verify the quadratic scaling relation C(n) = 1/2 n(n − 1) = Θ(n²), and extract the fundamental quadratic scaling coefficient a_quad using ordinary least-squares linear regression.

2. Abstract

Seven benchmark trials were generated across input sizes n = 10 to n = 70 elements (permutation pair space x = n(n − 1) from 90 to 4830 pairs). An ordinary least-squares regression of key comparisons C against permutation pair space yielded an empirical quadratic scaling coefficient of 0.5000 comparisons/pair, demonstrating exact agreement with the combinatorial identity C(n) = 1/2 n(n − 1) (difference = 0.0000%). The empirical telemetry proves that while Bubble, Selection, and Insertion Sort all share Θ(n²) worst-case comparison complexity, Selection Sort strictly minimizes memory bus write amplification to at most n − 1 element swaps (2n − 2 writes), compared to Bubble Sort's up to n(n − 1)/2 swaps (~3× writes per swap), explaining why Selection Sort is preferred in Flash/EEPROM architectures.

3. Apparatus and fixed settings

• Virtual Sorting Execution Engine & Register Profiler: Executes algorithmic sorting passes with deterministic instruction step tracking, recording every key comparison primitive and memory swap without non-deterministic operating system scheduling interference.
• Contiguous Random-Access Key Buffer: Allocates an in-memory array storing n numerical keys, providing O(1) indexed reads and writes for element comparisons and in-place positional swaps.
• Dual-Index Pointer Tracking Subsystem: Maintains hardware index pointers i (outer loop partition index) and j (inner scan cursor), delimiting the sorted prefix/suffix and highlighting the active candidate pair.
• Inversion Counter & Permutation Analyzer: Computes the initial Kendall-tau inversion distance I(A) = |{(i,j) : i < j and A[i] > A[j]}| of the input permutation, verifying that each adjacent swap reduces total inversions by exactly 1.
• Memory Bus Write Amplification Monitor: Tracks physical memory writes and cache line updates, distinguishing algorithms that minimize write cycles (Selection Sort: at most n-1 writes) from write-heavy routines (Bubble Sort).
• Pseudo-Random Permutation Generator: Synthesizes uniform random permutations, reverse-sorted adversarial sequences, and nearly sorted lists with controlled inversion densities to evaluate algorithmic adaptivity.
• Unsorted array initialized with randomized permutation of n distinct keys in range [1, 1000].
• Standard non-early-exit comparison tracking to isolate pure algorithmic loop bounds: C = n(n − 1) / 2.
• Hardware write bus tracking records discrete element swaps and memory assignments.
• Instruction cycle counters measure total comparative overhead independent of processor clock drift.

4. Theory and graph choice

Sorting algorithms represent foundational building blocks in computer systems, database query engines, and computational geometry. While advanced algorithms achieve O(n log n) scaling, elementary quadratic sorting algorithms—Bubble Sort, Selection Sort, and Insertion Sort—illustrate essential trade-offs between comparison counts, memory write amplification, adaptive early-exit capabilities, and algorithmic stability. In this laboratory, we empirically quantify the quadratic work profile C(n) = n(n − 1)/2 across varying input sizes, investigate permutation inversions, and analyze why adjacent-comparison sorting incurs an insurmountable Ω(n²) average-case lower bound.

The mathematical regression fits the linear model y = mx + b, where x = n(n − 1) represents the total permutation pair space in pairs, y = C represents discrete key comparisons, m represents the quadratic scaling coefficient a_quad, and b represents baseline comparison overhead. The gradient has physical units comparisons/pair.

5. Method

1. Initialize the contiguous memory buffer with n distinct numerical keys for the selected benchmark size n in [10, 20, 30, 40, 50, 60, 70]. Synthesize a randomized permutation using the Knuth-Fisher-Yates shuffle algorithm to ensure uniform distribution across all n! possible arrangements.
2. Pass the initial array through the inversion analyzer to calculate the baseline Kendall-tau distance I(A). Verify that for a randomized array, the expected inversion count approaches E[I] = n(n − 1) / 4.
3. Select the target sorting paradigm (Selection Sort for non-adaptive quadratic benchmark baseline, or Bubble/Insertion Sort). Initialize outer pass counter i = 0 and inner scanning pointer j = 0. Reset the atomic comparison register C and swap register S to 0.
4. Execute the inner scanning loop across the unsorted partition. In each step, perform a ternary key comparison between elements A[j] and A[j+1] (or A[j] and A[min_idx]). Increment the comparison counter C by 1. Highlight the candidate elements on the visual array canvas.
5. When out of order, execute an element swap or shift, incrementing the swap counter S. In Selection Sort, defer the swap until the end of the pass, placing the minimum element into index i. Mark the newly sorted boundary on the visual canvas.
6. Upon sorting completion (outer loop termination), record the final total comparison count C into the observation notebook. Repeat across all sample sizes n in [10, 20, 30, 40, 50, 60, 70]. Compute x = n(n − 1) and perform ordinary least-squares regression to extract the quadratic scaling coefficient a_quad.

6. Observations and calculation table

All benchmark observations use strictly controlled memory buffers. Values are recorded deterministically from the algorithmic comparator register. Residuals are computed relative to the ordinary least-squares regression line.

Download the sample observations (CSV) ↓

7. Worked calculation for one observation

8. Graph, gradient and final calculation

Circular markers represent empirical benchmark observations. The solid line represents the ordinary least-squares asymptotic linear fit.

9. Uncertainty and comparison

Percentage difference = |estimate − theoretical value| / |theoretical value| × 100 = 0.0000%.

For n = 7 benchmark observations, Σresidual² = 0.00000; s² = Σresidual²/(n − 2). Gradient standard error = √[s²/Σ(x − x̄)²] = 2.3367e-10. Intercept standard error = √[s²(1/n + x̄²/Σ(x − x̄)²)] = 5.9381e-07.

Propagating the fit parameters yields a fit standard error of 2.3367e-10 comparisons/pair, with an ideal coefficient of determination R² = 1.000000.

In combinatorial sorting analysis, the comparison count C(n) = n(n − 1)/2 for Selection Sort and worst-case Bubble Sort is an exact deterministic combinatorial identity. Unlike noisy analog experimental instrumentation, discrete step counting in virtual machine execution registers exhibits zero random measurement error. However, physical hardware execution is influenced by microarchitectural phenomena: (1) L1 data cache spatial locality, where contiguous in-place array iterations execute with ~1 ns latency; (2) Branch predictor mispredictions during conditional element checks (`if (A[j] < A[min])`), which stall superscalar execution pipelines by 15–20 clock cycles; (3) Memory bus write contention during element swaps, where Selection Sort's O(n) write profile heavily outperforms Bubble Sort's O(n²) write churn; and (4) CPU dynamic frequency scaling under continuous nested-loop arithmetic. Ordinary least-squares linear regression of observed comparisons against permutation pair space x = n(n − 1) yields an empirical scaling slope a_quad = 0.5000 comparisons/pair with zero residual error (R² = 1.00000), rigorously verifying the quadratic complexity bound Θ(n²).

10. Result and discussion

The empirical benchmark observations perfectly align with the combinatorial pair summation C(n) = ∑_{i=1}^{n-1} (n − i) = n(n − 1)/2. The slope m = 0.5000 confirms that exactly half of the directed pair space is compared in an unordered array. Furthermore, the inversion analysis demonstrates why any algorithm relying strictly on adjacent element swaps requires Ω(n²) comparisons on average, as each adjacent swap can eliminate at most one Kendall-tau inversion from an initial expectation of n(n − 1)/4 inversions. Finally, the hardware telemetry highlights the critical trade-off between comparisons and memory write amplification: Selection Sort achieves identical comparisons to Bubble Sort while reducing physical memory writes by a factor of over 35× at n = 70.

11. Precautions and limitations

• Verify whether the benchmark configuration employs early-exit optimization; disabling early-exit isolates pure combinatorial loop bounds C = n(n − 1)/2 across all permutations.
• When evaluating sorting stability, tag equal keys with auxiliary unique timestamps to detect any transposition of identical keys.
• In write-constrained systems, verify memory bus write amplification by tracking both comparison and swap counters.
• When measuring physical wall-clock execution time, ensure the processor frequency scaling governor is set to performance mode to prevent CPU throttling during nested loop execution.

The theoretical quadratic model evaluates atomic operation counts (comparisons C = n(n − 1)/2 and swaps). In physical microprocessors, execution time is heavily influenced by CPU branch prediction: in Selection Sort, updating the running minimum (`if (A[j] < A[min])`) causes unpredictable branch mispredictions on random data, stalling the pipeline. In Insertion Sort, sequential cache locality allows shifts to execute at near memory-bus wire speed for small n, creating a wide divergence between theoretical instruction counts and physical wall-clock performance. The theoretical comparison count for Selection Sort and worst-case Bubble Sort on an array of size n is exactly C(n) = ∑_{i=1}^{n-1} (n − i) = n(n − 1)/2. When plotted against the pair space x = n(n − 1), the theoretical slope is exactly a_quad = 0.5000 comparisons per pair, with an intercept of b = 0.0000. In contrast, memory swap counts differ dramatically across algorithms: Selection Sort performs at most n − 1 swaps regardless of input permutation (minimizing flash/EEPROM write wear), while worst-case Bubble Sort requires n(n − 1)/2 swaps. Insertion Sort adapts dynamically to existing order, requiring only O(n) comparisons on nearly sorted inputs.

12. Conclusion

This laboratory investigation quantitatively verified the asymptotic complexity and microarchitectural behavior of quadratic sorting algorithms. Through systematic benchmarking across arrays from 10 to 70 elements, we verified the quadratic scaling multiplier a_quad = 0.5000 comparisons/pair, matching theoretical predictions with an ideal R² = 1.00000. The investigation established the theoretical necessity of non-adjacent partition and exchange primitives (such as Quicksort and Heapsort) to overcome the Ω(n²) barrier imposed by pairwise adjacent transpositions.