/**
 * krq.c
 *   The K&R Quicksort.
 */

#include "krq.h"
#include "swap.h"

/**
 * kr_qsort: sort v[left]...v[right] into increasing alphabetical order.
 *   Note: Renamed to avoid conflict with qsort in stlib.h.
 */ 
void 
kr_qsort (char *v[], int left, int right)
{
  int i, last;

  /* If the array contains fewer than two elements, do nothing. */
  if (left >= right) 
    return;
  swap(v, left, (left + right)/2);
  last = left; 
  for (i = left+1; i <= right; i++) 
    if (strcmp (v[i], v[left]) < 0)
      swap(v, ++last, i); swap(v, left, last);
   kr_qsort (v, left, last-1); 
   kr_qsort (v, last+1, right);
} // kr_qsort

/**
 * sort:
 *   Sort using kr_qsort.  (This is not a solution to the assignment, since
 *   we have not rewritten the original.)
 */
void
sort (char *strings[], int size)
{
  kr_qsort (strings, 0, size-1);
}