Hi,

I don't know if you're permitted to accept late (re)submissions.  I sent
some
code last night which had a few bugs, which I fixed this morning.
Obviously,
I'd take the 20% penalty if I could, but I think the broken code will get
marked down more than 20%, so I'd have little to lose.  Obviously, if you
can't
accept this resubmission, please dismiss it out-of-hand.

/* COM1390 Programming Assignment 1 - Quantiles
   Chris Saia  <csaia@ccs.neu.edu>
*/

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/* I made this a #define so I could easily use smaller implementations of
   the program for testing. */
#define NKEYS 12

/* global variable keeping a running total of comparisons */
int comparisons = 0;

/* FN: Print out the array, for debugging purposes. */
void print_array(int mykeys[], int n)
{
  int loop;
  
  printf("Array = ");
  for(loop = 0; loop < n; loop++)
    printf("%d ", mykeys[loop]);
  printf("\n");
}

/* FN: Swap two elements in a given array. */
void swapelts(int mykeys[], int a, int b)
{
  int c;

  c = mykeys[a];
  mykeys[a] = mykeys[b];
  mykeys[b] = c;
  return;
}

/* FN: This function partitions the array of elements and returns the
   partitioning value to the caller.  It has the additional side-effect
   that the array is partitioned afterwards. */
int partition(int S[], int p, int r)
{
  int x, i, j;
  
  x = S[p];
  i = p - 1;
  j = r + 1;
  for(;;) {
    do {
      j--;
      comparisons++;
    } while (S[j] > x);
    do {
      i++;
      comparisons++;
    } while (S[i] < x);
    if(i < j)
      swapelts(S, i, j);
    else
      return j;
  }
}

/* FN: generate a random number between start and end, inclusive. */
int random(int start, int end)
{
  return start + (rand() % (abs(end - start) + 1));
}

/* FN: randomized-partition */
int rpartition(int S[], int p, int r)
{
  int i;

  i = random(p, r);
  swapelts(S, p, i);
  return partition(S, p, r);
}

/* FN: randomized-select */
int rselect(int S[], int p, int r, int i)
{
  int k, q;

  if(p == r)
    return S[p];
  q = rpartition(S, p, r);
  k = q - p + 1;
  if (i <= k)
    return rselect(S, p, q, i);
  return rselect(S, q + 1, r, i - k);
}

/* FN: This is the main function. */
int main(void)
{
  int n = NKEYS, k = 0, loop, index;
  int keys[n], newkeys[n];
  
  /* seed the random number generator */
  srand(time(NULL));

  /* populate the array of keys. */
  for(loop = 0; loop < n; loop++) {
    keys[loop] = 0;
    fflush(stdout);
    (void) scanf("%d", &keys[loop]);
  }

  /* find out which kth quantile we want */
  fflush(stdout);
  (void) scanf("%d", &k);

  /* print out the kth quantiles via selection */
  for(loop = 1; loop < n; loop++) {
    if(loop % (n / k) == 0) {
      printf("%d\n", rselect(keys, 0, n - 1, loop));
    }
  }

  /* tell the user how many comparisons all this took */
  printf("%d\n", comparisons);
  exit(0);
}