/* 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;
}