Arrays: Quicksort

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Aybekz
Neuling
Neuling
Beiträge: 3
Registriert: 18. Apr 2017 19:29

Arrays: Quicksort

Beitrag von Aybekz » 8. Jun 2017 11:48

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
Neuling
Neuling
Beiträge: 9
Registriert: 14. Mai 2017 15:21

Re: Arrays: Quicksort

Beitrag von Voleuro » 11. Jun 2017 01:34

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

Aybekz
Neuling
Neuling
Beiträge: 3
Registriert: 18. Apr 2017 19:29

Re: Arrays: Quicksort

Beitrag von Aybekz » 11. Jun 2017 14:25

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
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 9. Mai 2017 12:44

Re: Arrays: Quicksort

Beitrag von Vykyfikation » 20. Jun 2017 17:22

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!

joshimoo
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 25. Apr 2015 17:16

Re: Arrays: Quicksort

Beitrag von joshimoo » 21. Jun 2017 23:34

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

Antworten

Zurück zu „AuD: Programmieraufgaben“