selectionProblem.c

/* selection problem solution in C*/
#include<stdio.h>

/*swap two elements*/
void swap(int *a,int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}


/* recursivley partition the sub-arrays  */
int select(int A[], int iBegin, int iEnd, int I)
{
	int iPivot; // pivot index
	if (iBegin < iEnd)
	{	
		iPivot = partition(A, iBegin, iEnd);
		int k  = iPivot - iBegin +1;
		//k is number of elements in left side of partition, plus one for pivot element 
		
		if(I == k)
			return A[iPivot];//check if it is ith smallest
		// if ith min occurs in the left sub-array
		else if(I < k)
			return select(A, iBegin, iPivot-1, I);
		// if ith min occurs in the right sub-array
		else
			return select(A, iPivot+1, iEnd, I-k);

	}
}


/* 
    Takes last element in the array as pivot and reorder such that 
    smaller values to its left and larger or equal values to its right
	iBegin : Beginn index
	iEnd   : End index
 */
int partition(int A[], int iBegin, int iEnd)
{
	int pivotValue = A[iEnd];
	int storeIndex = iBegin;
	int i;
	for (i = iBegin; i < iEnd; ++i)
	{
		if(A[i] < pivotValue)
		{
			swap(&A[i], &A[storeIndex]);
			storeIndex++;
		}
	}
	swap(&A[iEnd], &A[storeIndex]);
	return storeIndex;
}

int main()
{
	int T,N,I;
	int A[200];
	int i,j;
	scanf("%d",&T);
	for(i=0; i<T; i++)
	{
		scanf("%d",&N);
		for(j=0; j<N; j++)
		{
			scanf("%d",&A[j]);
		}
		scanf("%d",&I);
		printf("%d\n",select(A,0,N-1,I));
	}
	return 0;
}