diff options
Diffstat (limited to '')
| -rw-r--r-- | report/qsort.c | 21 | ||||
| -rw-r--r-- | report/report.tex | 21 |
2 files changed, 42 insertions, 0 deletions
diff --git a/report/qsort.c b/report/qsort.c new file mode 100644 index 0000000..6877369 --- /dev/null +++ b/report/qsort.c @@ -0,0 +1,21 @@ +void quicksort(int arr[], int lo, int hi) { + if (lo >= 0 && hi >= 0 && lo < hi) { + int p = partition(A, lo, hi) + quicksort(A, lo, p) + quicksort(A, p + 1, hi) + } +} + +int partition(int arr[], int lo, int hi) { + int pivot = arr[lo]; + int i = lo - 1, j = hi + 1; + while (true) { + do { i++; } while (arr[i] < pivot); + do { j--; } while (arr[j] > pivot); + if (i >= j) break; + int temp = arr[i]; + arr[i] = arr[j]; + arr[j] = temp; + } + return j; +} 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} |