Selectionsort

Dadung
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 7. Mai 2017 13:08

Selectionsort

Beitrag von Dadung » 8. Jul 2017 15:17

Hallo,


ich habe 3 Fehler bei der Aufgabe und weiß nicht genau, wo diese liegen sollen:

mein code:

Code: Alles auswählen

{
   int l = array.length;
    
   while (l > 0){
        int m = 0;
        for (int j = 0; j < l; j++){
            if (array[j].compareTo(array[m]) > 0){
                m = j;
            }
        }
        if (m != (l - 1)){
        Listobject<T> c = array[m];
        array[m] = array[l - 1];
        array[l - 1] = c;
        }
        l--;
    }
    return array;
}
meine Fehler:
ntwort des Servers
Junitreport

Time – 100

Testcount – 10

Failurecount – 3

Ignorerecount – 0

Failurereport

Testheadder – basicTest_4_elemented_List_random_values(array.sort.tests_selectionSort_iterative.TestSelectionSort)

Message – Solution must be wrong. compareTo was called not often enough for selectionsort.

Trace

Failurereport

Testheadder – basicTest_for_sorting_like_selectionsort(array.sort.tests_selectionSort_iterative.TestSelectionSort)

Message – The input sequence was: [23, 41, 32, 510, 13, 130 ]Triangle-change was wrong. Test failed at iteration with index: 1 expected:<41> but was:<23>

Trace

Failurereport

Testheadder – basicTest_5_elemented_list_sorted(array.sort.tests_selectionSort_iterative.TestSelectionSort)

Message – Solution must be wrong. compareTo was called not often enough for selectionsort.

Trace
der triangle change ist mir bereits im Forum aufgefalle, scheinbar ist der Fehler bereits seit über einem Monat bekannt, warum gibt es dazu noch keine Hilfe?


dann habe ich noch die beiden Fehler, die mir sagen, dass ich nicht häufig genug compareTo aufrufe, hier kann ich nicht ganz nachvollziehen woran das liegen soll:

In jedem Durchlauf der inneren Schleife wird das größte Element des unsortierten Arrayteils gesucht. Hier gibt es l compareTo Aufrufe (meiner Meinung nach könnte ich sogar auch erst bei j = 1 anfangen, da ich das erste Element ja nicht mit sich selber vergleichen muss, aber das würde die Zahl der Vergleiche ja nur weiter reduzieren.).
Die äußere Schleife setzt dieses Element immer an das Ende des unsortierten Bereichs und verringert diesen dann um 1. Auch hier kann ich nicht mehr compareTo Aufrufe aus dem Hut zaubern, eher könnte ich sie auch hier noch verringern, da ein Array der Länge 1 nicht mehr unsortiert sein kann.




So, ich habe gerade eben mal meine "Verbesserungsideen", die ich zwischendrin verworfen hatte eingefügt und siehe da auf einmal werden alle Tests bestanden.

Folglich sollten bitte eigene Tests für zu viele compareTo Aufrufe eingesetzt werden, da es sehr verwirrend ist, wenn man gesagt bekommt man hätte zu wenige compareTo Aufrufe, obwohl man zu viele hat.


Außerdem hätte ich gerne eine Erklärung, was genau dieser "Triangle-Change" Test macht.




Viele Grüße
Tobias



EDIT:
hier noch der funktionierende Code:

Code: Alles auswählen

{
   int l = array.length;
    
   while (l > 1){
        int m = 0;
        for (int j = 1; j < l; j++){
            if (array[j].compareTo(array[m]) > 0){
                m = j;
            }
        }
        if (m != (l - 1)){
        Listobject<T> c = array[m];
        array[m] = array[l - 1];
        array[l - 1] = c;
        }
        l--;
    }
    return array;
}

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

Re: Selectionsort

Beitrag von goerlibe » 29. Aug 2017 11:14

für Querleser: iteration of triangle change probleme entstehen durch "falsche" iterationsrichtung und "falsche" Verwendung des Comparator, wobei "falsch" hier "anders als in der Referenz-Implementation" meint.
Hier ein Thread mit funktionierender Implementation und Diskussion zum fehlschlagenden Test
viewtopic.php?f=167&t=36244

Antworten

Zurück zu „Archiv“