diff options
Diffstat (limited to '')
| -rw-r--r-- | report/report.tex | 28 |
1 files changed, 24 insertions, 4 deletions
diff --git a/report/report.tex b/report/report.tex index 2f414b6..b14fcab 100644 --- a/report/report.tex +++ b/report/report.tex @@ -191,6 +191,9 @@ the array format. All functions in this program follow the x86 calling conventions, with a few exceptions where all registers are preserved. Below is a detailed explanation of some of the more interesting functions. +\subsection{Array maker} +\snippet{19}{46}{../src/array_maker.s} + \subsection{Insertion-sort} This is a classic implementation of the iterative insertion-sort. The function takes three arguments: address of the array of pointers to each coordinate, @@ -263,7 +266,8 @@ the output from the \textit{builtin} function \textit{sort}. 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 is shown +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}. \begin{figure}[H] \centering @@ -294,17 +298,17 @@ file is shown qsort\_reverse, qsort\_sorted} % -- O(n) - \addplot[domain=1:92709, samples=100, thick, densely dotted, black] + \addplot[domain=1:100000, samples=100, ultra thick, densely dotted, black] {(x * 1/18000000+0.0003)}; \addlegendentry{$\mathcal O(n)$} % -- O(nlogn) - \addplot[domain=1:92709, samples=100, thick, dotted, black] + \addplot[domain=1:100000, samples=100, ultra thick, dotted, black] {(x*ln(x)) * 1/80000000 + 0.0003}; \addlegendentry{$\mathcal O(n\log n)$} % -- O(n^2) - \addplot[domain=1:92709, samples=100, thick, dashed, black] + \addplot[domain=1:100000, samples=100, ultra thick, dashed, black] {(x*x) * 1/5000000000+0.0003}; \addlegendentry{$\mathcal O(n^2)$} @@ -314,6 +318,22 @@ file is shown sorted and reverse sorted data.}\label{fig:benchmark} \end{figure} +From \autoref{fig:benchmark} 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. + +Footnote + +isort\_random,1000000,386.935 +qsort\_random,1000000,0.148 +isort\_random,1000000,343.616 +qsort\_random,1000000,0.159 +isort\_random,1000000,384.022 +qsort\_random,1000000,0.155,0.146 + \section{Conclusion} |