/** find the Middle element in the Array without sorting it.
	 * This function uses a modified version of QuickSort, where we
	 * only consider the one half of the array.
	 * This is a recursive function where we look at some section of the array
	 * (Concerned Array) at a time.
	 *
	 * @param low = Loweset index of the Concerned Array
	 * @param high = Heighest index of the Concerned Array
	 * @param rank = The rank of the element in concerned array
	 */
	#include<stdio.h>
	
	int findElementAtRank(int arr[20], int low, int high, int rank){
	    int pivot = low;
	    int l=low;
	    int h = high;
	 
	    if(l<=h){
	        while(l<h){
	            while(arr[l]<=arr[pivot]) l++;
	            while(arr[h]>arr[pivot]) h--;
	 
	            if(l<h){
	                // Swapping the left and right
	                int temp = arr[l];
	                arr[l] = arr[h];
	                arr[h] = temp;
	            }
	        }
	        // Swapping the pivote with the high pointer
	        int temp = arr[pivot] ;
	        arr[pivot] = arr[h];	       
		 arr[h] = temp;
	    }
	 
	    if(rank < h){
	        return findElementAtRank(arr, low, h-1, rank);
	    }else if(rank > h ){
	        return findElementAtRank(arr, h+1, high, rank);
	    }else{
	        return arr[h];
	    }
	}
	
	int main()
	{
		int a[20],i,a_length,median_1,median_2;
		float median;
		printf("enter the length of the array\n");
		scanf("%d",&a_length);

		printf("enter the values\n");
		for(i=0;i<a_length;i++)
		scanf("%d",&a[i]);

		//finding the median 
		if(a_length%2==0)
		{
			median_1=findElementAtRank(a,0,a_length-1,a_length/2-1);
			median_2=findElementAtRank(a,0,a_length-1,a_length/2);
			median=(median_1+median_2)/2.0;// if array length is even then it is average of middle two elements
		}
		else
		{
			median=findElementAtRank(a,0,a_length-1,a_length/2);
		}
		
		printf("Median is %lf \n",median);

		return 0;
	}