/** 
 * Alex Cohn and Jordan Shkolnick
 * 3/9/10
 * CSC323: make
 * quicksort.c: A method to sort strings following the quicksort algorithm
**/
#include "quicksort.h"
#include "array-utils.h"
#include <string.h>
#include <stdlib.h>

/**
* Sort an array of characters using the quicksort algorithm.
* Adapted from Jon Bentley's Quicksort in Beauiful Code
*/
void 
quicksort (char *x[], int l, int u)
{
  int i, m;
	//If partition size is less than 0, we are done
  if (l >= u)
    return;
  //generate a random int ranging from from l to u for the pivot
	int randomval = random()%(u-l) + l;
  str_swap (x, l, randomval);
  m = l;
  for (i = l+1; i <=u; i++)
    {
      if (strcmp (x[i], x[l]) < 0)
        {	
          str_swap (x, ++m, i);
        } // if
    } // for
  str_swap(x, l, m);
  quicksort (x, l, m-1);
  quicksort (x, m+1, u);
}