median of medians not working properly

Question

I'm writing C code for the Median of Medians algorithm to find the kth smallest element in worst case linear time. I've checked my code for Quick Sort, Swapping, etc. Everything looks good but still it is not working properly every time.

Input given -

n=12 kth=7
A[]=53 22 65 18 89 45 42 63 99 11 36 55

Output -

Smallest at k=7 is 89

but output needs to be

Smallest at k=8 is 53

Function call -

med_of_medians(A,0,n-1,kth);

Code -

int med_of_medians(int A[], int a, int b, int kth)
{
if(a==b)
    return 0;
int n=(b-a+1),median,pos,rank;
int i,med[(n+4)/5];
for(i=0;i<n/5;i++)
    med[i]=find_median(A,(i*5)+a,((i+1)*5)-1);
if(n%5>0)
    med[i++]=find_median(A,(n/5)*5+a,b);
median=(i==1)?med[0]:find_median(med,0,i-1);
pos=partition(A,a,b,median);
rank=pos-a+1;   
if(rank==kth)
    return A[pos];
else if(rank>kth)
    return med_of_medians(A,a,pos-1,kth);
else
    return med_of_medians(A,pos+1,b,kth-pos-1);
}

Answer 1

You probably want to return A[a] in the first if:

if (a == b)
    return A[a];

There is missing a in the second index in the find_median call:

med[i]=find_median(A,(i*5)+a, a +((i+1)*5)-1);

and also a should be added for the new rank calculation (it should be kth - rank):

return med_of_medians(A,pos+1,b,kth-pos-1 +  a);