/**
 * Quicksort.c
 *   An implementation of Quicksort.
 */

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

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;
  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);

  // Recurse on the two sides
  Quicksort (values, border-1);
  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