/**
 * student-sort.c -
 *   K&R's Quicksort routine, updated for our arrays of students
 *   Additional documentation by SamR.
 */

// +---------+--------------------------------------------------------
// | Headers |
// +---------+

#include "student-sort.h"	// Make sure we match the signature


// +---------+--------------------------------------------------------
// | Helpers |
// +---------+

/**
 * swap (students, i, j): Swap the elements in positions i and j.
 */
static void
swap (struct student *students[], int i, int j)
{
  struct student *tmp = students[i];
  students[i] = students[j];
  students[j] = tmp;
} // swap

/**
 * kr_qsort: sort students[left]...students[right] into increasing order using
 *   comp to compare elements
 */ 
void 
kr_qsort (struct student *students[], 
          int left, int right, 
          int (*comp)(struct student *s1, struct student *s2))
{
  int i, last;

  // If the array contains fewer than two elements, do nothing.
  if (left >= right) 
    return;

  // Use the middle element as the pivot, which we put at the left.
  swap(students, left, (left + right)/2);
  last = left; 

  // Rearrange the elements so that large things are on the right
  for (i = left+1; i <= right; i++) 
    if ((*comp)(students[i], students[left]) < 0)
      swap(students, ++last, i); 

   // Put the pivot in the middle
   swap(students, left, last);

   // And recurse
   kr_qsort (students, left, last-1, comp); 
   kr_qsort (students, last+1, right, comp);
} // kr_qsort



// +--------------------+---------------------------------------------
// | Exported Functions |
// +--------------------+

void 
sort_students (struct student *students[], int size,
               int (*compare)(struct student *s, struct student *t))
{
  kr_qsort (students, 0, size-1, compare);
} // sort_students