/* Find the kth smallest element in a set of n elements.
   Lab1 for comp3600/comp6466 */


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

#define MAX 10000

static unsigned long counter;

/***************** Function Definitions ********************/

void insert_sort(int *A, int l, int h);
/* sort the elements in an array A[l..h-1] by increasing order */

int selection(int *A, int k, int n);
/* find the kth smallest element in an n-element array A */

/************************************************************/


/***************** insert sort subroutine *****************/

void insert_sort(int *A, int l, int h)
     /* sort the elements in A[l..h] in increasing order */
{
  int i, j, temp;

  ++counter;
  if ((l+1) < h) 
    for (j=l+1; j < h; j++)
      {
	++counter;
        temp = A[j];
        i=j-1;
        while ( (i > (l-1)) && (A[i] > temp) )
          {
	    ++counter;
            A[i+1]=A[i];
            i = i-1;
          }
        A[i+1]=temp;
      }
}

/*****************************************************************/


/********************* selection subroutine ********************/

int selection(int *A, int k, int n)
{ 
  int  i, j, l, p, r, x, K;
  int B[MAX]; /* Array B is used for storing the median sequence */
  int R1[MAX], R3[MAX]; 

  /* The elements in array A will be partitioned into 3 groups, */
  /* with the 1st and 3rd groups stored in arrays R1, R3. */
  /* The second group consists of a single value, so we just need
   * to remember how many elements it has and don't need to store it. */
  ++counter;
 
 if ( n <= 5 ) 
    {
     insert_sort(A, 0, n); /* sort the elements in the array */
     return (A[k-1]); /* the index of the array starts from 0 */
    };

 /* Otherwise, find the median sequence which will be stored in array B */

 K = n/5; /* the number of groups of 5 elements in A */ 
 if (K != 0) /* more than one group */
 for (j= 0; j < K; j++)
    {
      insert_sort(A, 5*j, 5*j+5 ); /* sort the elements for each group */
      B[j] = A[5*j+2]; /* the median of each group will be stored in B */
    };

 r = n % 5; /* The last group consisting of r elements */ 
 if (r != 0) 
   {
     insert_sort(A, n-r, n);
      B[K]=A[(n-r+r/2)]; 
      /* the median of the last group */
      K=K+1; /* the number of medians */ 
   };

 /* the median sequence B[0..K-1] */
  
  if (K > 1) 
     x = selection(B, ((K+1)/2), K); 
     /* find the median of elements in set B recursively */
    else x = B[K];
 /* x now is the median of elements in B */ 
 /* partition set A into three disjoint subsets R1, R2, and R3 using x */

  j = 0; /* the number of elements in A  less than   x  */
  p = 0; /* the number of elements in A  equal to    x  */
  l = 0; /* the number of elements in A  larger than x  */
 
 for (i=0; i < n; i++)
   {
     ++counter;
     if (A[i] < x)
          R1[j++]=A[i]; 
     if (A[i] == x ) 
          p++;    
     if (A[i] > x)     
          R3[l++]=A[i];
   }; 

 /****************************************************/
 /***** YOUR JOB is to finish this part ***********/
 /****************************************************/

 if (k <= j)
     return selection(R1,k,j);
 else if (k <= j + p)
     return x;
 else
     return selection(R3,k-j-p,l);

} 
/***************** end of the selection subroutine*************/



/************************* Main Program ****************/
int main( )
{ 
  int i, k, n;
  int A[MAX];

  printf("The number of elements is: ");
  scanf("%d", &n);

  if (n < 1 || n > MAX)
  {
     fprintf(stderr,"Sorry, n must be 1..%d and k must be 1..n.\n",MAX);
     exit(1);
  }
  for ( i=0; i< n; i++)
       A[i] = random();
  
  counter = 0;
  selection(A, 1+n/2, n);	

  printf("counter/n = %.4lf\n",(double)counter/(double)n);
}