K-ty najmniejszy element

0

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);
	}
}
0

W temacie powinno byc k-ty najwiekszy element

0
  

if (q == k) {
    std::cout << A[mid] << std::endl;
    return A[mid];
  }
//dla danych:
  int unSorted[]{2, 1, 5, 5, 7, 8, 15, 17, 20, 22, 32, 14};

  quickselect(unSorted, 0, 11, 1);
  quickselect(unSorted, 0, 11, 2);
  quickselect(unSorted, 0, 11, 4);

Zwraca:

1
2
5

W którym momencie w ogóle quickselect coś zwraca? On zawsze się będzie wywoływał tylko, kiedy wraca inta?

1 użytkowników online, w tym zalogowanych: 0, gości: 1