/* Find the kth smallest element in a set of n elements.
   Lab1 for comp3600 in 2006.  by Weifa Liang */
/* Trivial changes made by Brendan McKay for 2007. */

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

#define MAX 1000

/***************** 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;

  if ((l+1) < h) 
    for (j=l+1; j < h; j++)
      {
        temp = A[j];
        i=j-1;
        while ( (i > (l-1)) && (A[i] > temp) )
          {
            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. */
 
 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++)
   { 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 ***********/
 /****************************************************/

} 
/***************** 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);
  printf("The rank of the element to find is: ");
  scanf("%d", &k);

  if (n < 1 || n > MAX || k < 1 || k > n)
  {
     fprintf(stderr,"Sorry, n must be 1..%d and k must be 1..n.\n",MAX);
     exit(1);
  }
  printf("\n");
  for ( i=0; i< n; i++)
    {    
      printf("The %d%s element is: ",i+1,
	        i==0?"st": i==1?"nd": i==2?"rd": "th");
      scanf("%d", &A[i]);
    }
  printf ("\nThe %d%s smallest element is %d.\n",k,
	  k==1?"st": k==2?"nd": k==3?"rd": "th",
	  selection(A, k, n));	
}