/**
 * median.c
 *   The Quicksort-related technique for finding the median.
 */

#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

/**
 * Find the nth-largest value in values.
 */
int
nth (int values[], int size, int n)
{
  // 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);
  
  // Did we find the nth largest?
  if (n == border-1)
    return values[border-1];

  // Recurse on the appropriate size
  else if (n < border)
    return nth (values, border-1, n);

  else
    return nth (values+border, size-border, n-border);
} // nth

int
median (int values[], int size)
{
  return nth (values, size, (size-1)/2);
} // median

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

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

  printf ("The median is %d\n", median (values, argc-1));

  return 0;
} // main