/**
 * solution.c
 *   Your solution to the problem.  (That is, your more efficient
 *   implentation of ith_smallest.)
 */

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

#include <string.h>

#include "ith-smallest.h"
#include "swap.h"


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

static char *
ith_smallest_helper (char *strings[], int left, int right, int i)
{
  int j, last;

  swap(strings, left, (left + right)/2);
  last = left; 
  for (j = left+1; j <= right; j++) 
    if (strcmp (strings[j], strings[left]) < 0)
      swap(strings, ++last, j); 
  swap(strings, left, last);

  if (last == i)
    return strings[last];
  else if (i < last)
    return ith_smallest_helper (strings, left, last-1, i);
  else
    return ith_smallest_helper (strings, last+1, right, i);
} // ith_smallest_helper

char *
ith_smallest (char *strings[], int size, int i)
{
  return ith_smallest_helper (strings, 0, size-1, i);
} // ith_smallest