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. Explore interactive search algorithms, compare operation counts and analyse complexity scaling.
Ready to execute array size benchmark.
Adjust array size n, then execute benchmark.
Operation counts are generated deterministically by the exact algorithmic execution model. Modern hardware benchmarks additionally reflect cache line prefetching and branch misprediction penalties.
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.
Executes algorithmic sorting passes with deterministic instruction step tracking, recording every key comparison primitive and memory swap without non-deterministic operating system scheduling interference.
Allocates an in-memory array storing n numerical keys, providing O(1) indexed reads and writes for element comparisons and in-place positional swaps.
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.
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.
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).
Synthesizes uniform random permutations, reverse-sorted adversarial sequences, and nearly sorted lists with controlled inversion densities to evaluate algorithmic adaptivity.
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. Suggested independent settings: 10, 20, 30, 40, 50, 60, 70 elements.
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.
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.
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.
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.
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.
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.
Points are your recorded benchmark observations. The regression line validates Quadratic Sorting Algorithms complexity scaling.
| # | Array size n (elements) (elements) | Key comparisons C (comparisons) | Permutation pair space n(n − 1) (pairs) | Key comparisons C (operations) | Remove |
|---|
No readings yet. Execute a array size benchmark and record it.