Próbuję zaimplementować QuickSorta iteracyjnie na stosie z podziałem elementu metodą mediany, ale źle sortuje. Może ktoś zobaczy błąd którego ja nie widzę?
class QuickSort {
private long[] tabl;
public QuickSort(long[] tabl) {
this.tabl = tabl;
}
public void swap(int i, int j) {
long temp = tabl[i];
tabl[i] = tabl[j];
tabl[j] = temp;
}
long medianOf3(int L, int R) {
int C = (L + R) / 2;
if (tabl[L] > tabl[C]) {
swap(L, C);
}
if (tabl[L] > tabl[R]) {
swap(L, R);
}
if (tabl[C] > tabl[R]) {
swap(C, R);
}
swap(C, R - 1);
return tabl[R - 1];
}
int partition(int L, int R) {
long q = medianOf3(L, R);
int I = L-1; // L (po ++)
int J = R; // R-1 (po --)
while (true) {
while (tabl[++I] < q);
while (tabl[--J] > q);
if (I >= J) { // jeśli kolejność wskaźników się zmieni,
break; // dzielimy dane
} else { // kolejność nie uległa zmianie, a zatem
swap(I, J); // zamieniamy elementy A[i] i A[j]
}
}
// przenosimy element stanowiący oś podziału
swap(I, R - 1); // zamieniamy elementy A[i] i A[R]
return I; // zwracamy położenie podziału
}
void QuickSort() throws StosException {
int L = 0;
int R = tabl.length - 1;
Stos stos = new Stos(tabl.length);
int q = 0;
while (L < R || stos.isNotEmpty()) {
if (L < R) {
q = partition(L, R);
if (q - L < R - q) { // sprawdzam wielkość podzadania
stos.push(q + 1);
stos.push(R);
R = q - 1;
} else {
stos.push(L);
stos.push(q);
L = q;
}
} else {
R = stos.pop();
L = stos.pop();
}
}
}
}