Move qsort.cpp

1 files changed, 0 insertions, 100 deletions

diff --git a/qsort.cpp b/qsort.cpp
deleted file mode 100644
index d3e8c1d..0000000
--- a/qsort.cpp
+++ /dev/null
@@ -1,100 +0,0 @@
-/* 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;
-}