Quicksort recursive - bekomms nicht auf die Kette...

beta_tester_1001
Neuling
Neuling
Beiträge: 10
Registriert: 29. Mai 2017 17:12

Quicksort recursive - bekomms nicht auf die Kette...

Beitrag von beta_tester_1001 » 19. Jun 2017 00:23

Hab total keine Lust mehr. Die Tests haben anscheinend so knappe timeouts, dass es mal 2 und mal 4 erfolge gibt...
Der Code scheint mir viel zu lang und taugt trotzdem nicht.

Hilfe?!

Code: Alles auswählen

public Listobject<T>[] quicksort(Listobject<T>[] array) {
    // return null
    if (array == null)
        return null;
    // return same or length 1
    if ( sameInts(array) )
        return array;
    Listobject<T> tmp = null;
    // sort 2 elements and return
    if (array.length == 2) {
        if (array[0].compareTo(array[1]) < 0) {
            return array;
        } else {
            tmp = array[1];
            array[1] = array[0];
            array[0] = tmp;
            return array;
        }
    }

    int left = 1;
    int right = array.length - 1;
    // start sorting
    while (left < right) {
        if (array[left].compareTo(array[0]) <= 0 && left + 1 != right) {
            left++;
        }
        if (array[right].compareTo(array[0]) >= 0 && right - 1 != left) {
            right--;
        }
        if (array[left].compareTo(array[right]) > 0 ) {
            tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
        }
    }

    Listobject<T>[] pivot = new Listobject[1];
    pivot[0] = array[0];
    Listobject[] leftA = new Listobject[left - 1];
    for (int i = 1; i <= left; i++) {
        leftA[i - 1] = array[i];   
    }
    Listobject[] rightA = new Listobject[array.length - left];
    for (int i = right; i <= array.length - 1; i++) {
        leftA[i - right] = array[i];   
    }
    
    return combineArrays( leftA, pivot, rightA);
}

goerlibe
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:22

Re: Quicksort recursive - bekomms nicht auf die Kette...

Beitrag von goerlibe » 19. Jun 2017 08:49

Keine Zeit, das genau anzuschauen..

Mein Vorgehen war:

Abbruchbedingungen:

Code: Alles auswählen

if(array == null) return null;
if(array.length <= 1 || sameInts(array))  return array;
// unbedingt mit "<=" Länge 0 bedenken!
Schleife zum Zählen wie viele Elemente...
- kleiner
- gleich
- größer
... dem pivot (bei mir array[0]) waren

Arrays mit entsprechenden Größen erstellen.

Weitere Schleife, um die Elemente in den jeweiligen Arrays einzufügen.

Dann nur noch:

Code: Alles auswählen

return combine(quicks(smallerElements), quicks(equalElements), quicks(largerElements)) ;

beta_tester_1001
Neuling
Neuling
Beiträge: 10
Registriert: 29. Mai 2017 17:12

Re: Quicksort recursive - bekomms nicht auf die Kette...

Beitrag von beta_tester_1001 » 19. Jun 2017 20:50

Läuft, danke!

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

Re: Quicksort recursive - bekomms nicht auf die Kette...

Beitrag von Yogi » 11. Jul 2017 13:39

Hallo,

ich habe folgenden Code:

Code: Alles auswählen

{
    if (array != null) {
        Listobject<T>[] left = null;
        Listobject<T>[] middle = null;
        Listobject<T>[] right = null;
        if (array.length <= 1 || this.sameInts(array)) {
            return array;
        } else {
            Listobject<T> pivot = array[0];
            middle = new Listobject[1];
            middle[0] = pivot;
            for (int i = 1; i < array.length; i++) {
                if (pivot.compareTo(array[i]) < 0) {
                    Listobject<T>[] old_right = right;
                    if (old_right != null) {
                        right = new Listobject[old_right.length + 1];
                        for (int j = 0; j < old_right.length; j++) {
                            right[j] = old_right[j];
                        }
                        right[old_right.length] = array[i];
                    } else {
                        right = new Listobject[1];
                        right[0] = array[i];
                    }
                } else if (pivot.compareTo(array[i]) > 0) {
                    Listobject<T>[] old_left = left;
                    if (old_left != null) {
                        left = new Listobject[old_left.length + 1];
                        for (int j = 0; j < old_left.length; j++) {
                            left[j] = old_left[j];
                        }
                        left[old_left.length] = array[i];
                    } else {
                        left = new Listobject[1];
                        left[0] = array[i];
                    }
                } else {
                    Listobject<T>[] old_middle = middle;
                    middle = new Listobject[old_middle.length + 1];
                    for (int j = 0; j < old_middle.length; j++) {
                        middle[j] = old_middle[j];
                    }
                    middle[old_middle.length] = array[i];
                }
            }
            if (left == null && right != null) { 
                Listobject<T>[] sorted = quicksort(right);
                Listobject<T>[] result = new Listobject[array.length];
                for (int i = 0; i < array.length; i++) {
                    if (i < middle.length) result[i] = middle[i]; 
                    else result[i] = sorted[i - middle.length];
                }
                return result;
            } else if (left != null && right == null) {
                Listobject<T>[] sorted = quicksort(left);
                Listobject<T>[] result = new Listobject[array.length];
                for (int i = 0; i < array.length; i++) {
                    if (i < sorted.length) result[i] = sorted[i];
                    else result[i] = middle[i - sorted.length];
                }
                return result;
            } else if (left != null && right != null)
                return this.combineArrays(quicksort(left), middle, quicksort(right));
            else return middle;
        }
    }
    return null;
}
und die Test sagen:
Antwort des Servers
Junitreport
Time – 181
Testcount – 8
Failurecount – 3
Ignorerecount – 0
Failurereport
Testheadder – dynamicTest_CountOfSteps(array.sort.tests_quicksort_recursive.Quicksort_array_recursive_test)
Message – test timed out after 50 milliseconds
Trace
Failurereport
Testheadder – boundaryTest_sortedArray(array.sort.tests_quicksort_recursive.Quicksort_array_recursive_test)
Message – In sorted should be pivot-element number: 2 be element with key: 21. But the result was key: 4. The testarray was: [1, 2, 3, 4, 5, 6, 7 ] expected:<3> but was:<4>
Trace
Failurereport
Testheadder – statictest(array.sort.tests_quicksort_recursive.Quicksort_array_recursive_test)
Message – Array index out of range: 5
Trace
Ich sehe keinen Fehler in meinem Code. Kann mir jemand einen Tipp geben was hier schief läuft? Kann es sein, dass die Tests wieder Falsch sind?

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

Re: Quicksort recursive - bekomms nicht auf die Kette...

Beitrag von Yogi » 11. Jul 2017 13:51

Ok ich habe eine sehr lange Laufzeit, da ich die Elemente der 3 Mengen nicht zu Beginn gezählt habe, aber ich verstehe nicht, wieso die anderen zwei Test fehlschlagen?

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

Re: Quicksort recursive - bekomms nicht auf die Kette...

Beitrag von Yogi » 12. Jul 2017 03:44

Ich habe mein Code überarbeitet, indem ich die Länge der 3 Teilarrays zu Beginn zähle, aber ich bekomme immer noch:
Antwort des Servers
Junitreport
Time – 51
Testcount – 8
Failurecount – 2
Ignorerecount – 0
Failurereport
Testheadder – boundaryTest_sortedArray(array.sort.tests_quicksort_recursive.Quicksort_array_recursive_test)
Message – In sorted should be pivot-element number: 2 be element with key: 21. But the result was key: 4. The testarray was: [1, 2, 3, 4, 5, 6, 7 ] expected:<3> but was:<4>
Trace
Failurereport
Testheadder – statictest(array.sort.tests_quicksort_recursive.Quicksort_array_recursive_test)
Message – Array index out of range: 5
Trace
Ich verstehe nicht was bei diesem Testfall schief geht. Hat jemand hier Failurecount - 0 ?

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

Re: Quicksort recursive - bekomms nicht auf die Kette...

Beitrag von Yogi » 12. Jul 2017 12:46

Hier ist die Ursache meines Problems: viewtopic.php?f=167&t=36519&p=176036#p176020

Antworten

Zurück zu „Archiv“