Move qsort.cpp

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;
+}