report(qsort): add part about qsort

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}