report(evaluation): Benchmarking comparisons plot and tex

1 files changed, 63 insertions, 4 deletions

diff --git a/report/report.tex b/report/report.tex
index 5eeddee..2777bd0 100644
--- a/report/report.tex
+++ b/report/report.tex
@@ -274,7 +274,7 @@ Given all of the tests pass, we can then run \textit{benchmark.sh}, which times
 how long it takes for our program to run with each test file for each algorithm,
 and saves the result in a \textit{csv} file. The results of this \textit{csv}
 file, together with functions asymptotically equivalent to $\mathcal O(n)$, $\mathcal O(n\log
-n)$ and $\mathcal O(n^2)$, is shown on \autoref{fig:benchmark}.
+n)$ and $\mathcal O(n^2)$, is shown on \autoref{fig:benchmarktime}.
 
 \begin{figure}[H]
     \centering
@@ -322,17 +322,76 @@ n)$ and $\mathcal O(n^2)$, is shown on \autoref{fig:benchmark}.
 
       \end{axis}
     \end{tikzpicture}
-    \caption{Benchmarking data from Insertionsort and Quicksort for both random,
-    sorted and reverse sorted data.}\label{fig:benchmark}
+    \caption{Benchmarking data for timing from Insertionsort and Quicksort for
+    both random, sorted and reverse sorted data, plotted with a logarithmic y
+    axis}\label{fig:benchmarktime}
 \end{figure}
 
-From \autoref{fig:benchmark} we see that Insertionsort behaves as expected
+From \autoref{fig:benchmarktime} we see that Insertionsort behaves as expected
 with a best-case runtime of $\mathcal O(n)$ when the input is sorted, and a
 worst-case runtime of $\mathcal O(n^2)$, when the input reversely sorted or
 random. We also see that Quicksort behaves as expected with a best-case runtime
 of $\mathcal O(n\log n)$ when the input is random, and a worst-case runtime of
 $\mathcal O(n^2)$ when the input is either sorted or reversely sorted.
 
+It is however also possible to count the number of comparisons for each
+algorithm. This plot can be seen on \autoref{fig:benchmarkcomp}. Here we clearly
+see that, for example, Insertionsort has exactly $n$ comparisons, when sorting
+and already sorted array of $n$ elements. We also see that Quicksort with random
+elements, matches - within a scalar - with $n\log n$.
+
+\begin{figure}[H]
+    \centering
+    \begin{tikzpicture}
+        \begin{axis}[
+                xlabel={size({$n$})},
+                ylabel={seconds},
+                ymode=log,
+                % xmode=log,
+                width=\textwidth,
+                legend pos=south east,
+                clip mode=individual,
+                mark size=1pt,
+                scatter/classes={
+                    isort_random={mark=*,red},
+                    isort_reverse={mark=*,magenta},
+                    isort_sorted={mark=*,pink},
+                    qsort_random={mark=*,teal},
+                    qsort_reverse={mark=*,blue},
+                    qsort_sorted={mark=*,cyan}
+                }
+            ]
+
+        % -- Scatter plot --
+        \addplot[scatter, only marks, scatter src=explicit symbolic] table 
+            [x=size, y=comp, meta=type, col sep=comma]
+            {../test/benchmark_comparisons.csv};
+        \legend{isort\_random, isort\_reverse, isort\_sorted, qsort\_random,
+            qsort\_reverse, qsort\_sorted}
+
+        % -- O(n)
+        \addplot[domain=1:100000, samples=100, ultra thick, densely dotted, black]
+          {(x)};
+            \addlegendentry{$n$}
+
+        % -- O(nlogn)
+        \addplot[domain=1:100000, samples=100, ultra thick, dotted, black]
+          {(x*ln(x))};
+        \addlegendentry{$n\log n$}
+
+        % -- O(n^2)
+        \addplot[domain=1:100000, samples=100, ultra thick, dashed, black]
+          {(x*x)};
+        \addlegendentry{$n^2$}
+
+      \end{axis}
+    \end{tikzpicture}
+    \caption{Benchmarking data for comparisons from Insertionsort and Quicksort
+    for both random, sorted and reverse sorted data. The y axis is logarithmic,
+    and the reference lines are not asymptotic but
+    exact.}\label{fig:benchmarkcomp}
+\end{figure}
+
 \subsection{Nonalgorithmic factors}
 Although the asymptotic run times are caused by the algorithms themselves,
 the total run times are also greatly affected by the concrete implementations