diff options
Diffstat (limited to 'report/report.tex')
| -rw-r--r-- | report/report.tex | 21 |
1 files changed, 21 insertions, 0 deletions
diff --git a/report/report.tex b/report/report.tex index 358ac87..7ef00ba 100644 --- a/report/report.tex +++ b/report/report.tex @@ -19,6 +19,8 @@ breaklines]{asm}{#1}} \newcommand{\snippet}[3]{\inputminted[firstline=#1,lastline=#2,linenos, xleftmargin=1.5em, breaklines]{asm}{#3}} +\newcommand{\snippetC}[3]{\inputminted[firstline=#1,lastline=#2,linenos, +xleftmargin=1.5em, breaklines]{c}{#3}} % ---------------------------- \begin{document} @@ -209,6 +211,25 @@ allocate space for the array Go through each element in the array and create a pointer that points to a pair in the pairwise data. +\subsection{quick-sort} +The quick-sort 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 +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. +This continues until the pointers cross, effectively partitioning the array +into two segments. + +\begin{figure}[H] + \snippetC{1}{22}{qsort.c} + \caption{Pseudo code for quick-sort algorithm in c-style}\label{fig:qsort} +\end{figure} + +In order to compare two values in the array. The algorithm \textit{dereferences} +the element, and access the element at the given \textit{index}. +To swap two \textit{sub-arrays}, it simply swap their \textit{pointers} +in the pointer-array. \section{Evaluation} |