diff options
Diffstat (limited to 'report')
| -rw-r--r-- | report/report.tex | 68 |
1 files changed, 68 insertions, 0 deletions
diff --git a/report/report.tex b/report/report.tex index 9192c5b..5b0d40e 100644 --- a/report/report.tex +++ b/report/report.tex @@ -52,20 +52,88 @@ actual runtime to their theoretical runtimes. These datasets will be ranging fro cases with duplicates or nearly sorted lists. \section{Design} +\begin{itemize} + \item 3 stage process, read $\rightarrow$ sort $\rightarrow$ print + \item Array format +\end{itemize} + \begin{figure}[H] \centering \includegraphics[scale=0.6]{flowchart.drawio.png} \caption{Program flow} \label{fig:flowchart} \end{figure} + +\subsection{The Array} +In order to be a litte more general, and make our program easily expandable to +different types of data, we wanted to create out own array datatype, that +allowes us to sort something more abstract, with respect to a key in that +abstract object. +To do this we settled on an array of memory addresses, that point to where the +abstract objects are, see \autoref{fig:array}. These object would in practice +also be represented as +arrays. With this we can specify which index (key) in the sub-arrays we want to +sort by, and then when we swap elements in the array, we simply swap the memory +addresses around. + +\begin{figure}[H] + \centering + \begin{tikzpicture} + \draw (0,0) rectangle (4,1); % outer box + \node at (-0.5,0.5) {$A=$}; + + % vertical dividers + \draw (1,0) -- (1,1); + \draw (2,0) -- (2,1); + \draw (3,0) -- (3,1); + \node at (0.5,0.5) {$p_1$}; + \node at (1.5,0.5) {$p_2$}; + \node at (2.5,0.5) {$\cdots$}; + \node at (3.5,0.5) {$p_n$}; + + \draw (0.1,2) rectangle (0.8,5); + \node at (0.5,2.5) {$e_{11}$}; + \node at (0.45,3.6) {$\vdots$}; + \node at (0.5,4.5) {$e_{1m}$}; + + \draw (1.1,2) rectangle (1.8,5); + \node at (1.5,2.5) {$e_{21}$}; + \node at (1.45,3.6) {$\vdots$}; + \node at (1.5,4.5) {$e_{2m}$}; + + \draw (3.1,2) rectangle (3.8,5); + \node at (3.5,2.5) {$e_{n1}$}; + \node at (3.45,3.6) {$\vdots$}; + \node at (3.5,4.5) {$e_{nm}$}; + + \draw[->] (0.5,1.1) -- (0.5,1.9); + \draw[->] (1.5,1.1) -- (1.5,1.9); + \draw[->] (3.5,1.1) -- (3.5,1.9); + \end{tikzpicture} + \caption{The format of the array $A$, where $p_n$ is the $n^\text{th}$ + memory address, pointing to an array where $e_nm$ is the $m^\text{th}$ + element of the $n^\text{th}$ element in $A$.} + \label{fig:array} +\end{figure} + \section{Implementation} + \section{Evaluation} +\begin{itemize} + \item Test insertion-sort + \item Test quick-sort + \item Benchmark insertion-sort vs. quick-sort random data + \item Benchmark insertion-sort vs. quick-sort sorted data + \item Benchmark insertion-sort vs. quick-sort unsorted data +\end{itemize} + \begin{tikzpicture} \begin{axis}[xlabel={size},ylabel={seconds}] \addplot[only marks] table [x=size, y=real, col sep=comma] {../benchmark_results.csv}; \end{axis} \end{tikzpicture} + \section{Conclusion} \end{document} |