Sortieralgorithmus

[LeonInfo19]

Hallo, ich versuche gerade MergeSort gemäß Pseudocode für generische Typen zu implementieren. Ich habe dabei Probleme mit der Merge-Methode.

    private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int mid, int q) {

        Object[] tmp = new Object[q-p+1];
        
        
        int i = p;
        int j = mid+1;
        int k = 0;
        while (i <= mid && j <= q) {
            if (a.get(i).compareTo(a.get(j))<=0) {
                tmp[k] = a.get(i);
                i++;
            }
            else {
                tmp[k] = a.get(j);
                j++;
                k++;
            }
            
            if (i <= mid && j > q) {
                while (i <= mid) {
                    tmp[k++] = a.get(i);
                    i++;
                }
            }
            else {
                while (j <= q) {
                    tmp[k++] = a.get(j);
                    j++;
                }   
            }
            for (k = 0; k < tmp.length; k++) {
            a[k+p] = (T)(tmp[k]);
            }
       }
    }

Wie löse ich dabei den Fehler mit der compareTo Methode?
Wie bekomme ich in der letzten Zeile diese Zuweisung hin. Ich habe es mal in Array Notation gelassen.

 

[kneitzel]

Wieso machst Du tmp zu einem Array von Object. Object implementiert kein Comparable. Du hast Elemente vom Typ T also nutz das auch entsprechend.

 

[LeonInfo19]

Soll ich dann statt dem Object-Array eine ArrayList erstellen?

 

[LeonInfo19]

Falsch

 

[LeonInfo19]

Danke ich habe meine Fehler gefunden

 

[LeonInfo19]

Ok es tut sich doch noch ein Problem auf. Der Algo sortiert nicht richtig. Wo liegt denn der Fehler:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
        
        mergesort(list, 0, list.size()-1);
        
    }   
    private static <T extends Comparable<? super T>> void mergesort (List<T> list, int i, int j) {
        if (j-i < 1) return;
        int mid = (i+j)/2;
        mergesort(list, i, mid);
        mergesort(list, mid+1, j);
        merge(list, i, mid, j);
    }

    private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r){
        
        int half=q-p+1;
        int otherhalf=r-q;
        
        List<T> left=new ArrayList<T>();
        List<T> right=new ArrayList<T>();
        
        for(int i=0; i<half;i++) {
            left.add(i,a.get(p+i));
        }
        for(int i=0; i<otherhalf;i++) {
            right.add(i,a.get(q+i+1));
        }
        
        int leftindex,rightindex,resultindex;
        leftindex=rightindex=resultindex=0;
        // ein Array ist nichtleer
        while(leftindex<left.size() || rightindex<right.size()) {
            
            //beide Arrays haben Elemente
            if(leftindex<left.size() && rightindex<right.size()) {
                
                //beide Arrays enthalten Elemente
                if(left.get(leftindex).compareTo(right.get(rightindex))<=0) {
                    
                    a.set(resultindex,left.get(leftindex));
                    resultindex++;
                    leftindex++;
                }
                else {
                    a.set(resultindex,right.get(rightindex));
                    resultindex++;
                    rightindex++;
                }
            }
            //linkes enthält Elemente
            else if(leftindex< left.size()) {
                a.set(resultindex,left.get(leftindex));
                resultindex++;
                leftindex++;
            }
            //rechtes enthält Elemente
            else if(rightindex< right.size()) {
                a.set(resultindex,right.get(rightindex));
                resultindex++;
                rightindex++;
                
            }   
        }
        
    }

 

[LeonInfo19]

Kann vllt jmd schauen, warum der Algo nicht richtig sortiert. Der Fehler müsste egtl nur in 3. Hilfsmethode liegen?

 

[kneitzel]

Hast Du den Algorithmus mal von Hand durchgespielt? Oder einen Debugger bemüht? Wenigstens mal geschaut, was das Ergebnis ist und überlegt, wie die falschen Werte zustande kommen könnten? (Am Fehlerbild kann man oft auch einiges erkennen!)

Du hast schon den Verdacht, dass es die merge Funktion sein müsste (Die andere Methode hat ja auch kaum Inhalt ), also solltest Du die einmal genau unter die Lupe nehmen und schauen, welche Werte er wie schreibt.

Wenn man etwas sinnvollere Namen für die Variablen nehmen würde, dann wäre es aber evtl. auch etwas einfacher zu erkennen. a, i, j, p, q, r sagen extrem wenig aus!

Ansonsten ist es oft hilfreich, ein komplettes Beispiel zu bringen, welches man testen kann. Oft genug haben wir keine Lust, selbst etwas zu basteln. Wobei es hier auch ohne ausprobieren ging .

PS: In Deinem ersten Code ist der Fehler aus dem letzen Code übrigens noch nicht drin wenn ich das richtig gesehen habe.

 

[LeonInfo19]

Hallo, ja ich habe ihn von Hand durchgespielt und sehe den Fehler nicht. Du siehtst auch keinen offensichtlichen Fehler?
Die Variablen stammen vom Pseudocode aus unserer Vorlesung. Daran habe ich mich orientiert. Aber du hast Recht, dass sie verwirrend sind.
Ein einfaches Beispiel wäre folgendes:

public static void main(String [] args) {
        
    ArrayList a=new ArrayList();
    a.add(5);
    a.add(6);
    a.add(1);
    a.add(4);
    System.out.println(a);
    sort(a);
    System.out.println(a);

    }

Als Ergebnis erhalte ich:
[5, 6, 1, 4]
[1, 1, 4, 4]

D.h also, dass die Zahlen doppelt gespeichert werden. Irgendwo wird wsl ein Index nicht inkrementiert.

 

[kneitzel]

Doch, der Index wird inkrementiert, aber der Offset stimmt nicht.

Vergleiche einfach einmal die folgenden Codeausschnitte:

Aus dem ersten Code von Dir (Mal vom Casting und so abgesehen):

a[k+p] = (T)(tmp[k]);

Und dann aus dem aktuellen Code:

leftindex=rightindex=resultindex=0;
a.set(resultindex,right.get(rightindex));

 

[LeonInfo19]

Ich sehe es nicht. Die Hilfsindizes sind mit 0 wls richtig initialisiert. Sie sollen ja nur das Feld Schrittweise auffüllen. Aber der resultindex kann es auch nicht sein. Ich fülle ja mein sortiertes Feld von 0 an auf?

 

[kneitzel]

Wenn Du merge(array, startIndex, mittelIndex, endIndex) aufrufst, dann willst Du doch die Felder startIndex - endIndex bearbeiten!

In den temporären Array nimmst Du auch die Werte entsprechend aus diesem Bereich.
Aber dann schreibst Du die immer in die Felder 0....

 

[LeonInfo19]

Dann muss ich meine Indizes ander initialisieren?

 

[kneitzel]

Bist Du den Algorithmus einmal von Hand durchgegangen? Sortier manuell einmal ein Array { 7, 5, 3, 2, 1 }. Du kannst ja ganz normal die Aufrufe durchgehen auf einem Zettel.
Also es wird sort aufgerufen mit dem Array und dann wird mergesort aufgerufen mit (Array, 0, 4)
- j-i ist nicht kleiner als 1.
- mid = (0+4) / 2 = 2
=> es wird mergesort (array,0, 2) aufgerufen
==> j-i ist nicht kleiner als 1
==> mid = (0+2)/2 = 1
==> es wird mergesort (array, 0, 1) aufgerufen
===> j-i nicht < 1
===> mid = (0+1)/2 = 0
====> es wird mergesort(array, 0, 0) aufgerufen
=====> j-i < 1 => return!
====> es wird mergesort(array, 1, 1) aufgerufen
=====> j-i < 1 => return!
====> es wird merge(array, 0, 0, 1) aufgerufen
=====> Hier darfst Du einmal weiter machen ... Du kannst das auch gerne mit Stift und Zettel machen, das macht es evtl. einfacher und übersichtlicher!

Dann solltest Du zum einen den Fehler erkennen und auch, was evtl. geändert werden muss.

 

[LeonInfo19]

Ok danke. Ich gehe es dann später durch und melde mich. Habe jetzt vl. Vielen Dank erstmal.

 

[LeonInfo19]

Hallo kneitzel. Sorry für die späte Antwort. Ich habe den Fehler gefunden. Ich muss den resultindex=p setzen.

 

[kneitzel]

Ja genau! Sehr gut.

Oder wenn Du es auf 0 gelassen hättest, dann hättest Du auch resultindex+p verwenden können (So war es in der ersten Version, die Du gezeigt hattest: resultindex war da die Variable k und du hattest dann a[k+p].)

 

[LeonInfo19]

Ja oder so. Vielen Dank, dass du mich dazu gebracht hast, nochmal alles zu überdenken