aboutsummaryrefslogtreecommitdiff
path: root/impls/qsort.cpp
diff options
context:
space:
mode:
authorAryadev Chavali <aryadev@aryadevchavali.com>2024-07-17 20:12:07 +0100
committerAryadev Chavali <aryadev@aryadevchavali.com>2024-07-17 20:12:07 +0100
commitf7f106195a5caa905e73bef19119f5e59f4d3f2b (patch)
tree4285fd43acb8a52498600b00ef053c493c553926 /impls/qsort.cpp
parent262ab3fefa5c2c1ad15a2724d1cc9b87b503ca58 (diff)
downloadalgorithms-f7f106195a5caa905e73bef19119f5e59f4d3f2b.tar.gz
algorithms-f7f106195a5caa905e73bef19119f5e59f4d3f2b.tar.bz2
algorithms-f7f106195a5caa905e73bef19119f5e59f4d3f2b.zip
Move qsort.cpp
Diffstat (limited to 'impls/qsort.cpp')
-rw-r--r--impls/qsort.cpp100
1 files changed, 100 insertions, 0 deletions
diff --git a/impls/qsort.cpp b/impls/qsort.cpp
new file mode 100644
index 0000000..d3e8c1d
--- /dev/null
+++ b/impls/qsort.cpp
@@ -0,0 +1,100 @@
+/* qsort.cpp
+ * Date: 2024-06-22
+ * Author: Aryadev Chavali
+ * Commentary: The inplace O(nlog(n)) sortitng algorithm. Originally designed
+ * in C, hence the lack of iostream.
+ */
+#include <cstdio>
+#include <cstdlib>
+
+#define ARR_SIZE(XS) (sizeof(XS) / sizeof((XS)[0]))
+#define SWAP(A, B) \
+ do \
+ { \
+ (A) ^= (B); \
+ (B) ^= (A); \
+ (A) ^= (B); \
+ } while (0)
+
+#define TEST_SIZE 20
+
+void print_arr(int *arr, int size)
+{
+ printf("{");
+ for (int i = 0; i < size - 1; ++i)
+ printf("%d, ", arr[i]);
+ printf("%d}", arr[size - 1]);
+}
+
+void quicksort(int *arr, int arr_size)
+{
+#ifdef TRACE
+ printf("before, arr=");
+ print_arr(arr, arr_size);
+ printf("\n");
+#endif
+ // Optimisation: for small arr_size, a different sort like the
+ // bubble sort may be better, instead of initialising new stack
+ // frames.
+ if (arr_size < 2)
+ return;
+ // Optimisation: Use some heuristics to figure out a better pivot
+ // than some constant choice of element.
+ int pivot = 0;
+ int pivot_value = arr[0];
+ for (int i = 1; i < arr_size; ++i)
+ {
+ if (arr[i] <= pivot_value)
+ {
+ if (i != pivot)
+ SWAP(arr[i], arr[pivot]);
+ ++pivot;
+ }
+ }
+
+#ifdef TRACE
+ printf("after, arr=");
+ print_arr(arr, arr_size);
+ printf("\n");
+#endif
+ // Optimisation: Use a stack to do this instead of recursion.
+ //
+ // This algorithm is similar to a pre order traversal/dfs, in this
+ // case on an array where left and right partition are children
+ // nodes to the original array node. Also with recursion there's a
+ // real risk for very large ARR_SIZE of running out of space in the
+ // call stack.
+ if (pivot != 0)
+ quicksort(arr, pivot);
+ if (pivot < arr_size - 1)
+ quicksort(arr + pivot + 1, arr_size - pivot - 1);
+}
+
+int main(void)
+{
+ int arr[TEST_SIZE] = {0};
+ const int size = TEST_SIZE;
+
+ // Generate a completely reverse ordered list
+ /*for (size_t i = 0; i < size; ++i) */
+ /* arr[TEST_SIZE - i - 1] = i;*/
+
+ // Generate a list where the first half is completely sorted and the
+ // other half is in reverse order.
+ for (size_t i = 0; i < size / 2; ++i)
+ arr[i] = i;
+ for (size_t i = size / 2; i < size; ++i)
+ arr[TEST_SIZE - (i - size / 2) - 1] = i;
+
+ printf("Before: ");
+ print_arr(arr, size);
+ printf("\n");
+
+ quicksort(arr, size);
+
+ printf("After: ");
+ print_arr(arr, size);
+ printf("\n");
+
+ return 0;
+}