/**
 * sorter.c
 *   In implementation of Quicksort.
 */

#include <stdio.h>
#include <stdlib.h>
#include "reorder.h"

void
print_int_array (int values[], int size)
{
  int i;

  if (size == 0)
    {
      printf ("{}");
      return;
    }

  printf ("{%3d", values[0]);
  for (i = 1; i < size; i++)
    printf(",%3d", values[i]);
  printf ("}");
} // print_int_array

void
swap (int values[], int i, int j)
{ 
  int temp = values[i];
  values[i] = values[j];
  values[j] = temp;
} // swap

void
Quicksort (int values[], int size)
{
  if (size <= 1)
    return;

  // Pick a random pivot
  int pos = rand () % size;
  
  printf ("ORIGINAL: ");
  print_int_array (values, size);
  printf ("\n");
  printf ("PIVOT   : %d @ %d.\n", values[pos], pos);

  // Pick a pivot and put it at position 0
  swap (values, 0, pos);

  // Reorder into small and large
  int border = reorder (values, size, values[0]);

  // Put the pivot in the middle.  Note that we know that border has to
  // be at least 1, since, values[0] contains the pivot.
  swap (values, 0, border-1);

  printf ("BORDER  : %d\n", border);
  printf ("REORDER : ");
  print_int_array (values, size);
  printf ("\n");

  // Recurse on the two sides
  printf ("SORTING LEFT\n");
  Quicksort (values, border-1);
  printf ("SORTING RIGHT\n");
  Quicksort (values+border, size-border);
} // Quicksort

int
main (int argc, char *argv[])
{
  int values[argc];
  int i;

  for (i = 1; i < argc; i++)
    values[i-1] = atoi (argv[i]);

  Quicksort (values, argc-1);

  // Print out everything
  for (i = 1; i < argc; i++)
    printf ("%5d\n", values[i-1]);

  return 0;
} // main