Arrays: Quicksort

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

[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.

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.

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
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

[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

[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
Aber danke auf jeden Fall für die Lösung!

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