quickSort iteracyjnie, gdzie błąd?

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

jeżeli program się kończy i wyświetla jakieś dane, ale źle posortowane, to podejrzewam że procedura dzieląca jest błędna... spróbuj:

while (true) {
            while (tabl[I] < q) ++I;
            while (tabl[J] > q) --J;
            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]
            }
        }

Dokładnie tak, program wyrzuca wyniki, ale źle posortowane dla pewnych danych, dla innych wszystko jest okej. Zmieniłem znak w partition, ale teraz dostaję nieskończoną pętlę.

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
    }

Nie powinno być swap(tab[I],tab[J])?swap (I,J) zamieni indeksy a nie fizyczne elementy tablicy,tak samo swap(I,R-1)

Lewuaza napisał(a):

Nie powinno być swap(tab[I],tab[J])?swap (I,J) zamieni indeksy a nie fizyczne elementy tablicy,tak samo swap(I,R-1)

Patrząc na metodę swap, która pobiera indeksy i na jej podstawie zamienia elementy tablicy, nie mogę się zgodzić. Chyba, że czegoś nie zrozumiałem, to proszę, popraw mnie.

Może przedstawię problem nieco inaczej. Mam taką implementację, gdzie przy obliczaniu elementu do podziału stosuję najbardziej prawy element tablicy. Ta implementacja działa. Chciałbym ją zoptymalizować dodając medianę trzech elementów dla obliczania elementu do podziału. Niestety używając podanej funkcji, tablica wynikowa jest błędna.

Wersja z najbardziej prawym elementem:

class QuickSort {

    private long[] tab;

    public QuickSort(long[] tabl) {
        this.tab = tabl;
    }

    public void swap(int i, int j) {
        long temp = tab[i];
        tab[i] = tab[j];
        tab[j] = temp;
    }

    int partition(int L, int R) {
        long q = 0;

        q = tab[R];
        int I = L - 1;            // L (po ++)
        int J = R;              // R-1 (po --)
        while (true) {
            while (tab[++I] < q);
            while (J > L && tab[--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);                            // zamieniamy elementy A[i] i A[R]
        return I;                                   // zwracamy położenie podziału
    }

    void QuickSort() throws StosException {
        int L = 0;
        int R = tab.length - 1;
        Stos stos = new Stos(tab.length);
        int q = 0;

        while (L < R || stos.isNotEmpty()) {
            if (L < R) {
                q = partition(L, R);
                if (q - L < R - q) {
                    stos.push(q + 1);
                    stos.push(R);
                    R = q - 1;
                } else {
                    stos.push(L);
                    stos.push(q - 1);
                    L = q + 1;
                }

            } else {
                R = stos.pop();
                L = stos.pop();
            }
        }
    }
}

Wersja z medianą:

class QuickSort {

    private long[] tab;

    public QuickSort(long[] tabl) {
        this.tab = tabl;
    }

    public void swap(int i, int j) {
        long temp = tab[i];
        tab[i] = tab[j];
        tab[j] = temp;
    }

    long medianOf3(int L, int R) {
        int C = (L + R) / 2;

        if (tab[L] > tab[C]) {
            swap(L, C);
        }

        if (tab[L] > tab[R]) {
            swap(L, R);
        }

        if (tab[C] > tab[R]) {
            swap(C, R);
        }

        swap(C, R - 1);
        return tab[R - 1];

    }

    int partition(int L, int R) {
        long q = 0;

        q = medianOf3(L, R);
        int I = L - 1;            // L (po ++)
        int J = R;              // R-1 (po --)
        while (true) {
            while (tab[++I] < q);
            while (J > L && tab[--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);                            // zamieniamy elementy A[i] i A[R]
        return I;                                   // zwracamy położenie podziału
    }

    void QuickSort() throws StosException {
        int L = 0;
        int R = tab.length - 1;
        Stos stos = new Stos(tab.length);
        int q = 0;

        while (L < R || stos.isNotEmpty()) {
            if (L < R) {
                q = partition(L, R);
                if (q - L < R - q) {
                    stos.push(q + 1);
                    stos.push(R);
                    R = q - 1;
                } else {
                    stos.push(L);
                    stos.push(q - 1);
                    L = q + 1;
                }

            } else {
                R = stos.pop();
                L = stos.pop();
            }
        }
    }
}

Rozwiązałem problem samodzielnie. Błąd był w metodzie medianOf3 i dotyczył indeksowania. Wstawiam dla potomnych.

    long medianOf3(int L, int R) {
        int C = (L + R) / 2;

        if (tab[L] > tab[C]) {
            swap(L, C);
        }

        if (tab[L] > tab[R]) {
            swap(L, R);
        }

        if (tab[C] > tab[R]) {
            swap(C, R);
        }

        return tab[R];

    }

    int partition(int L, int R) {
        
        long q = 0;
        q = medianOf3(L, R);
        int I = L - 1;            // L (po ++)
        int J = R;              // R-1 (po --)
        while (true) {
            while (tab[++I] < q);
            while (tab[--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);                            // zamieniamy elementy A[i] i A[R]
        return I;                                   // zwracamy położenie podziału
    }

    void QuickSort() {
        int L = 0;
        int R = tab.length - 1;
        Stos stos = new Stos(tab.length);
        int q = 0;

        while (L < R || stos.isNotEmpty()) {
            if (L < R) {
                q = partition(L, R);
                if (q - L < R - q) {
                    stos.push(q + 1);
                    stos.push(R);
                    R = q - 1;
                } else {
                    stos.push(L);
                    stos.push(q - 1);
                    L = q + 1;
                }

            } else {
                R = stos.pop();
                L = stos.pop();
            }
        }
    }