Mam nastepujacy kod korzystajacy z funkcji partition na wyznaczenie k-tego najmniejszego elementu. Czy moglby ktos mi powiedziec czemu to nie dziala ? Szczegolnie zauwazylem ze majac np 10-elementowa tablice wypelniona takimi liczbami
-2,-3,5,-4,9,13,7,-8,80,4
To gdy podam k=1 to wypisze mi -4, a gdy podam k=2 to wypisze -8.
Tak jakby w ostatnim kroku nie wykonywala sie funkcja partition.
int partition(int A[],int l,int r) {
int pivot=A[(l+r) / 2];
int i=l;
int j=r;
while(i<j) {
while(A[i]<pivot) i++;
while(A[j]>pivot) j--;
if(i<j) {
swap(A[i],A[j]);
i++;
j--;
}
}
return j;
}
int quickselect(int A[],int l,int r,int k) {
int mid = partition(A,l,r);
int q = mid-l+1; // ilosc elementow lacznie z mid
if(q==k) return A[mid];
else if(q>k) {
return quickselect(A,l,mid-1,k);
}
else {
return quickselect(A,mid+1,r,k-q);
}
}