Seite 1 von 1

Arrays: Quicksort

Verfasst: 8. Jun 2017 11:48
von Aybekz
Hallo,
ich habe mich mal an die Quicksort-Aufgabe unter dem Arrays-Reiter gewagt. Mein Code besteht auch 7 von 8 Tests, der einzige Failerreportzeigt mir jedoch ein "timed out after 50 milliseconds" an. Ich nehme also an, dass ich die Vorgabe an die Komplexität nicht erfülle. Könnte sich jemand meinen Code ansehen und mir einen Tipp geben, wie ich das effizienter gestalten kann?
Vielen Dank im Vorraus!

Code: Alles auswählen

{
    if (array == null) return null;
    if (array.length <= 1 || sameInts(array)) return array;
    
    int counterL = 0;                                                           //length of left subarray
    int counterR = 0;                                                           //length of right subarray
    for(int i = 1; i < array.length; i++){
        if(array[i].compareTo(array[0]) < 0){
            counterL++;
        }
        else{
            counterR++;
        }
    }
    
    Listobject[] left  = new Listobject[counterL];
    Listobject[] right = new Listobject[counterR];
    
    int i1 = 0;                                                                 //pointer for left
    int i2 = 0;                                                                 //pointer for right
    
    Listobject[] pivot = new Listobject[1];
    pivot[0] = array[0];
    
    for(int i = 1; i<array.length; i++){
        if(array[i].compareTo(array[0]) < 0){
            left[i1] = array[i];
            i1++;
        }
        if(array[i].compareTo(array[0]) >= 0){
            right[i2] = array[i];
            i2++;
        }
    }
    return combineArrays(quicksort(left) ,pivot, quicksort(right));
}

Re: Arrays: Quicksort

Verfasst: 11. Jun 2017 01:34
von Voleuro
Hallo,

Habe deine Lösung gefixt. Du musst dein Pivot Element am anfang speichern und dann nicht array.compareTo(array[0]) sondern array.compareTo(pivotElementVariable) schreiben. Damit sparst du ein paar Calls, was im Endeffekt deinen Timeout error verhindert. :D

Ich habe eine komplett andere Implementierung gewählt in der ich ein zusätzliches Array für Equal wähle und dieses dann im für den Fall ".compareTo(pivot) == 0" gefüllt und dieses in combineArrays als mittleres Array verwendet. Warum deine und meine Implementierung genauso funktionieren kann ich dir aber nicht sagen. :shock:

Alles in allem bin ich allerdings nur anhand deines Codes auf einen Fehler gekommen, der mich für über zwei Stunden genervt hat. So ist es von gravierender Wichtigkeit, dass man die Compare Aufrufe als "array.compareTo(pivot)" und nicht, wie es auch Sinn machen würde, als "pivot.compareTo(array)" schreibt. Wenn man dies tut erscheinen nur irgendwelche Fehlermeldungen deren Sinn sich mir auch nach wiederholten Lesen nicht ergibt :roll:
Warum dies überhaupt wichtig ist mag mir mal bitte jemand erklären..
Alles in allem machen solche "kryptischen Fehlermeldungen" die Benutzung von Codemonkeys einfach nur frustrierend und zeitraubend. Bitte tut etwas dagegen!

Und für alle die es interessiert, hier ist noch meine Implementierung:

Code: Alles auswählen

public Listobject<T>[] quicksort(Listobject<T>[] array)
{
    if(array == null) {
        return null;
    }
    if(array.length <= 1) {
        return array;
    }
    
    if(sameInts(array)) {
        return array;
    }
    
    Listobject pivot = array[0];
    int smaller = 0;
    int bigger = 0;
    int equal = 1;
    
    for(int i=1;i<array.length;i++) {
        //int cmp = pivot.compareTo(array[i]);
        int cmp = array[i].compareTo(pivot);  //WARNUNG NUTZE BEIDE COMPARES NICHT UMGEKEHRT
        if(cmp < 0) {
            smaller++;
        }
        else if(cmp == 0) {
            equal++;
        }
        else {
            bigger++;
        }
    }
    
    Listobject[] arraySmall = new Listobject[smaller];
    Listobject[] arrayEqual = new Listobject[equal];
    Listobject[] arrayBig = new Listobject[bigger];
    
    int counterSmall = 0;
    int counterBig = 0;
    int counterEqual = 0;
    
    for(int i=0;i<array.length;i++) {
        //int cmp = pivot.compareTo(array[i]);
        int cmp = array[i].compareTo(pivot);  //WARNUNG NUTZE BEIDE COMPARES NICHT UMGEKEHRT
        if(cmp < 0) {
            arraySmall[counterSmall] = array[i];
            counterSmall++;
        }
        else if(cmp == 0) {
            arrayEqual[counterEqual] = array[i];
            counterEqual++;
        }
        else {
            arrayBig[counterBig] = array[i];
            counterBig++;
        }
    }

    return combineArrays(quicksort(arraySmall),quicksort(arrayEqual),quicksort(arrayBig));
}

Liebe Grüße,
Kai

Re: Arrays: Quicksort

Verfasst: 11. Jun 2017 14:25
von Aybekz
Vielen Danke für die HIlfe, jetzt funktioniert alles zumindest laut Codemonkeys!
Ich ging eigentlich davon aus, dass das Erstellen der Pivot Variablen in jeder Schleife langsamer wäre, als der direkte Zugriff auf das entsprechende Element im Array, aber jetzt wo ich so darüber nachdenke, macht dein Fix doch mehr Sinn :)

Re: Arrays: Quicksort

Verfasst: 20. Jun 2017 17:22
von Vykyfikation
Wow, da hätte ich noch lange nach meinem Fehler suchen können...
Hat jemand eine Ahnung, warum man unbedingt array.compareTo(pivot) machen muss?
Hatt überall pivot.compareTo(array) gehabt :D
Aber danke auf jeden Fall für die Lösung!

Re: Arrays: Quicksort

Verfasst: 21. Jun 2017 23:34
von joshimoo
@Aybekz:
dein Algorithmus ist nicht korrekt, da es sich hierbei um 3Way Quicksort handelt.
Mal dir mal den Rekursionsbaum fuer zum Beispiel: [6, 1, 6, 6, 9]
und vergleiche diesen mit dem Baum von Voleuro
Was fällt auf?

@Voleuro / Vykyfikation:
ob pivot.compareTo(elem) oder elem.compareTo(pivot) ist egal, es muessen dann nur die groesser/kleiner vergleiche invertiert werden.

@Alle:
Annahme der compareTo aufruf waere teuer, wie könnte man den unten stehen code optimieren?
Besteht dieser dann noch die Tests?

@Nabla Entwickler:
Ein moeglicher Verbesserungsvorschlag: statt die Zeit zu messen welche bei dem einen Test mit 50ms knapp bemessen ist.
bietet es sich bei den Nabla Aufgaben an das man die compare/merge/swap/etc aufrufe hookt und mitzaehlt daraus laesst sich dann die Komplexitäts Klasse ableiten.

Code: Alles auswählen

{
    if(array == null) { return null; }
    if(sameInts(array)) { return array; }
    
    int l = 0;
    int r = 0;
    int m = 0;
    Listobject pivot = array[0];
     
    for(int i = 0; i < array.length; i++) {
        int c = array[i].compareTo(pivot);
        if(c > 0) { r++; }
        else if (c < 0) { l++; }
        else { m++; }
    }
    
    Listobject[] left = new Listobject[l];
    Listobject[] right = new Listobject[r];
    Listobject[] mid = new Listobject[m];
    
    for(int i = 0; i < array.length; i++) {
        Listobject elem = array[i];
        int c = elem.compareTo(pivot);
        if(c > 0) { right[right.length - r--] = elem; }
        else if (c < 0) { left[left.length - l--] = elem; }
        else { mid[mid.length - m--] = elem; }
    }
    
    return combineArrays(quicksort(left), mid, quicksort(right));
}