Медиана медиан не работает должным образом

Question

Я пишу код C для алгоритма Медиана медиан, чтобы найти k-й наименьший элемент в наихудшем линейном времени. Я проверил свой код для быстрой сортировки, замены и т. Д. Все выглядит хорошо, но каждый раз он не работает должным образом.

Вход дан -

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

Выход -

Smallest at k=7 is 89

но вывод должен быть

Smallest at k=8 is 53

Вызов функции -

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

Код -

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

Вы, вероятно, хотите вернуться A[a] во-первых if:

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

Там отсутствует a во втором индексе в find_median вызов:

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

а также a должны быть добавлены для расчета нового ранга (это должно быть kth - rank):

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