aboutsummaryrefslogtreecommitdiff
path: root/report
diff options
context:
space:
mode:
authormithe24 <mithe24@student.sdu.dk>2025-10-29 19:59:36 +0100
committermithe24 <mithe24@student.sdu.dk>2025-10-29 22:01:36 +0100
commit4574728416114e3fdcdb82b2850c9cefc01f531a (patch)
tree15d3a50778532794691b6a82a85a2388f82167b5 /report
parent315fdaa546fd1ec81deb1f2749b8e8410293d19e (diff)
downloadsorter-4574728416114e3fdcdb82b2850c9cefc01f531a.tar.gz
sorter-4574728416114e3fdcdb82b2850c9cefc01f531a.zip
Wrapping text?
Diffstat (limited to 'report')
-rw-r--r--report/report.tex58
1 files changed, 39 insertions, 19 deletions
diff --git a/report/report.tex b/report/report.tex
index 2777bd0..3935462 100644
--- a/report/report.tex
+++ b/report/report.tex
@@ -11,6 +11,7 @@
\usepackage{float}
\usepackage{caption}
\usepackage{subcaption}
+\usepackage{wrapfig}
\geometry{a4paper}
@@ -130,17 +131,7 @@ datasets, while insertion sort is more suitable for small or nearly sorted
cases, which is another great motivation to understand what is really
happening when these algorithms are executed, and how the dataset affects them.
-\subsection{Sorting Format}
-In order to be a little more general, and make our program easily expandable to
-different types of data, we wanted to create our own array datatype, that
-allows 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 objects
-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]
+\begin{wrapfigure}[15]{r}{0.5\textwidth}
\centering
\begin{tikzpicture}
\draw (0,0) rectangle (4,1); % outer box
@@ -178,7 +169,24 @@ in the array, we simply swap the memory addresses around.
memory address, pointing to an array where $e_{nm}$ is the $m^\text{th}$
element of the $n^\text{th}$ array in $A$.}
\label{fig:array}
-\end{figure}
+\end{wrapfigure}
+\subsection{Sorting Format}
+In order to be a little more general, and make our program easily expandable to
+different types of data, we wanted to create our own array datatype, that
+allows us to sort something more abstract, with respect to a key in that
+abstract object.
+\smallskip
+
+\noindent
+To do this we settled on an array of memory addresses, that
+point to where the abstract objects are, see \autoref{fig:array}.
+\smallskip
+
+\noindent
+These objects 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.
\section{Implementation}
This four phase design has been converted into Assembly code using the x86\_64
@@ -205,7 +213,6 @@ $i^\text{th}$ pair in the array points to. The psudocode for this can be seen on
from this psudocode, hence the psudocode instead of assembly. This also makes it
easier to understand.}
-\vspace{10pt}
\begin{algorithm}[H]
\DontPrintSemicolon % optional: removes ;
\SetAlgoNoLine
@@ -230,23 +237,36 @@ easier to understand.}
\caption{Pseudocode for \texttt{array\_maker}}\label{fig:arraymaker}
\end{algorithm}
+\newpage
+
+\begin{wrapfigure}[22]{r}{0.6\textwidth}
+ \snippetC{1}{22}{qsort.c}
+ \caption{Pseudo code for quick-sort algorithm in c-style}\label{fig:qsort}
+\end{wrapfigure}
\subsection{Quicksort}
The quicksort implementation uses \textbf{Hoare partition scheme},
a \textit{two-way partitioning} approach two pointers scan from opposite ends
-of the array toward the middle. The left pointer advances rightward while
+of the array toward the middle.
+\smallskip
+
+\noindent
+The left pointer advances rightward while
pointing at elements smaller than the \textit{pivot}, and the right pointer
advances leftward while pointing at elements larger than the \textit{pivot}.
When both pointers both pointers points at misplaced elements, they swap them.
+\smallskip
+
+\noindent
This continues until the pointers cross, effectively partitioning the array
into two segments.
+\medskip
-\begin{figure}[H]
- \snippetC{1}{22}{qsort.c}
- \caption{Pseudo code for quick-sort algorithm in c-style}\label{fig:qsort}
-\end{figure}
-
+\noindent
In order to compare two values in the array. The algorithm \textit{dereferences}
the element, and access the element at the given \textit{index}.
+\smallskip
+
+\noindent
To swap two \textit{sub-arrays}, it simply swap their \textit{pointers}
in the pointer-array.