/*
 * To compute and print the median of the medians of separate 5 blocks of a 25-element array,
 * and compare it with the median of the entire array.
 * @author-Karan Narain(karan@iitk.ac.in)
 *
*/

#include<stdio.h>
int select(int A[], int l, int r, int i)
{
	int k,j, temp;
	for(k=l;k<r-1;k++)
	for(j=k+1;j<r;j++)
	{
	if(A[j]<A[k])
	{
	temp=A[k];
	A[k]=A[j];
	A[j]=temp;
        }
        }
	//return ith smallest from lower limit
	return A[l+i-1];	
}
int main()
{
	int j,A[25],i;
	int tempmeds[5],tm,m;
	printf("Enter the 25 elements of the array\n");
	for(i=0;i<25;i++)
	scanf("%d",&A[i]);

	printf("The array you entered is\n");
	for(i=0;i<25;i++)
	printf("%d   ",A[i]);
	printf("\n");
	//Intermediate medians
	for(i=0;i<5;i++)
	{
		tempmeds[i]=select(A,5*i,5*(i+1),3);
		printf("The median of block number %d is %d\n",i+1,tempmeds[i]);
	}
	//median of medians
	tm=select(tempmeds,0,4,3);

	//median of the entire array
	m=select(A,0,24,13);

	printf("The median of intermediate medians is %d and the median of the entire array is %d\n",tm,m);
		
	return 0;
}