Quicksort recursive - Unterschied zwischen pivot.compareTo(elem) und elem.compareTo(pivot)?

mlang
Neuling
Neuling
Beiträge: 3
Registriert: 28. Apr 2017 11:44

Quicksort recursive - Unterschied zwischen pivot.compareTo(elem) und elem.compareTo(pivot)?

Beitrag von mlang » 11. Jul 2017 19:29

Hallo zusammen,

ich habe bei meiner Quicksort-Lösung festgestellt, dass es scheinbar einen Unterschied macht, ob ich pivot.compareTo(elem) oder elem.compareTo(pivot) schreibe. Rein theoretisch müsste ich ja eigentlich wenn ich diese Schreibweise umdrehe einfach nur alle < und > jeweils invertieren und die Tests sollten genauso laufen. Das ist aber hier nicht der Fall:
1. Versuch: 6/8 Tests bestanden

Code: Alles auswählen

{if (array == null) return null;
if (array.length <= 1) return array;
if (sameInts(array)) return array;

Listobject<T> piv = array[0];
int l = 0;
int m = 1;
int r = 0;

for (int i = 1; i < array.length; i++){
    int c = piv.compareTo(array[i]);
    if (c == 0) m++;
    if (c < 0) r++;
    if (c > 0) l++;
}


int x = 0;
int y = 0;
int z = 0;

Listobject<T>[] smaller = new Listobject[l];
Listobject<T>[] pivot = new Listobject[m];
Listobject<T>[] bigger = new Listobject[r];

for (int v = 0; v < array.length; v++){
    int d = piv.compareTo(array[v]);
    if (d == 0) {
        pivot[y] = array[v];
        y++;
    }
        if (d < 0) {
        bigger[z] = array[v];
        z++;
    }
        if (d > 0) {
        smaller[x] = array[v];
        x++;
    }
}

return combineArrays(quicksort(smaller), pivot, quicksort(bigger));
}
Jetzt drehe ich die Schreibweise um

Code: Alles auswählen

//aus 
piv.compareTo(array[i]) 
//wird 
array[i].compareTo(piv) 
//und die darauf folgenden < und > werden invertiert

Und plötzlich funktioniert alles:

Code: Alles auswählen

{if (array == null) return null;
if (array.length <= 1) return array;
if (sameInts(array)) return array;

Listobject<T> piv = array[0];
int l = 0;
int m = 1;
int r = 0;

for (int i = 1; i < array.length; i++){
    int c = array[i].compareTo(piv);
    if (c == 0) m++;
    if (c > 0) r++;
    if (c < 0) l++;
}


int x = 0;
int y = 0;
int z = 0;

Listobject<T>[] smaller = new Listobject[l];
Listobject<T>[] pivot = new Listobject[m];
Listobject<T>[] bigger = new Listobject[r];

for (int v = 0; v < array.length; v++){
    int d = array[v].compareTo(piv);
    if (d == 0) {
        pivot[y] = array[v];
        y++;
    }
        if (d > 0) {
        bigger[z] = array[v];
        z++;
    }
        if (d < 0) {
        smaller[x] = array[v];
        x++;
    }
}

return combineArrays(quicksort(smaller), pivot, quicksort(bigger));
}
Irgendwas übersehe ich dabei, oder?

Yogi
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 19. Okt 2006 11:09
Kontaktdaten:

Re: Quicksort recursive - Unterschied zwischen pivot.compareTo(elem) und elem.compareTo(pivot)?

Beitrag von Yogi » 12. Jul 2017 12:10

Ich kann dies bestätigen. Seit ich es bei mit umgedreht habe funktioniert mein Code.
Antwort des Servers
Junitreport
Time – 62
Testcount – 8
Failurecount – 0
Ignorerecount – 0
compareTo arbeitet irgendwie fehlerhaft.

Antworten

Zurück zu „Archiv“