MergeSort funktioniert nicht

[raffi]

Hallo, ich sitze immernoch an derselben Aufgabe aus diesem Thread:
http://www.java-forum.org/java-basics-anfaenger-themen/85200-adjazenzliste-leer.html

Habe jetzt aber ein Problem mit dem Ordnen des Feldes, in dem die Namen der Orte, 11 Stück, stehen. Das Einlesen-Problem habe ich gelöst, wobei das Feld schon von anfang an kein Problem war. Ich sehe aber bei meinem Quelltext keine Fehler. Feld sieht gefüllt so aus:
Dresden Riesa Döbeln Chemnitz Flöha Olbernhau Bärenstein Aue Schwarzenberg Johangeorgenstadt Zwickau

Meine MergeSort Methoden sind folgende:

public void mergeSort (Knoten[] staedte, int start, int ende) {
		int mitte;
		if (start < ende) {
			mitte = (start + ende) / 2;
			mergeSort(staedte, start, mitte);
			mergeSort(staedte, mitte+1, ende);
			merge(staedte, start, mitte+1, ende);
		}
	}
	
	public void merge (Knoten[] staedte, int linksPos, int rechtsPos, int rechtsEnde) {
		int linksEnde = rechtsPos - 1;
		int help = linksPos;
		int anz = rechtsEnde - linksPos + 1;
		int i;
		temp = new String[anz];
		while (linksPos <= linksEnde && rechtsPos <= rechtsEnde) {
			if (staedte[linksPos].getStadtname().compareTo(staedte[rechtsPos].getStadtname()) <= 0) {
				temp[help] = staedte[linksPos].getStadtname();
				linksPos++;
				help++;
			}
			else {
				temp[help] = staedte[rechtsPos].getStadtname();
				rechtsPos++;
				help++;
			}
		}
		while (linksPos <= linksEnde) {
			temp[help] = staedte[linksPos].getStadtname();
			linksPos++;
			help++;
		}
		while (rechtsPos <= rechtsEnde) {
			temp[help] = staedte[rechtsPos].getStadtname();
			rechtsPos++;
			help++;
		}
		for (i = 0; i < anz; i++) {
			System.out.println(temp[i]);
		}
	}

aufgerufen durch:

mergeSort(staedte, 0, staedte.length-1);

Beim Debuggen tritt schon der erste fehler auf, und zwar das anz nur 2 ist. Aber dies müsste doch eigentlich 12 sein, damit auch temp voll gefüllt werden kann!? Und wenn ich diese Länge manuell einsetze funktioniert das ganze zwar reibungslos aber die Ausgabe ist natürlich total falsch:
null
Dresden
null
null
Dresden
null
null
null
null
null
null
null
null
Chemnitz
Dresden
Flöha
null
null
null
null
null

mfg und danke schonmal

 

[Marco13]

Erstmal vorneweg: Ich gehe davon aus, dass es Teil der Aufgabe ist, das ganze von Hand zu progammieren!? Ansonsten kann man einfach
Arrays.sort(staedte, ...);
aufrufen...

Beim Debuggen tritt schon der erste fehler auf, und zwar das anz nur 2 ist.
Das kann schon sein, da du das vermutlich in der untersten Rekursionsstufe angesehen hast.

Der erste Tipp um das leichter nachvollziehen zu können wären jetzt eingerückte(!) debug-Ausgaben:

public void mergeSort (Knoten[] staedte, int start, int ende, String intent) 
{
    System.out.println(indent+"mergeSort von "+start+" bis "+ende+" auf "+Arrays.toString(staedte));

        int mitte;
        if (start < ende) {
            mitte = (start + ende) / 2;
            mergeSort(staedte, start, mitte, indent+"    ");
            mergeSort(staedte, mitte+1, ende, indent+"    ");
            merge(staedte, start, mitte+1, ende, indent+"    ");
        }
    }
    
    public void merge (Knoten[] staedte, int linksPos, int rechtsPos, int rechtsEnde, String indent) 
    {
        System.out.println(indent+"merge von "+linksPos+" bis "+rechtsPos+" ende "+rechtsEnde+" auf "+Arrays.toString(staedte));
        ....


        ...
        System.out.println(indent+"merge von "+linksPos+" bis "+rechtsPos+" ende "+rechtsEnde+" ergibt "+Arrays.toString(staedte));
    }

 

[raffi]

Hallo, ja es soll natürlich per Hand programmiert werden...
Also ich habs mal noch etwas abgeändert und mir nochmal die debugging Schritte angeschaut. Er fängt eigentlich ganz gut an, aber eine Zählvariable springt dann drüber hinaus. Erstmal der leicht abgeänderte Quelltext:

public void mergeSort_aufruf(Knoten[] staedte) {
        String[] temp = new String[staedte.length];
        mergeSort(staedte, 0, staedte.length - 1, temp);
    }
	
	public void mergeSort (Knoten[] staedte, int start, int ende, String[] temp) {
		int mitte;
		if (start < ende) {
			mitte = (start + ende) / 2;
			mergeSort(staedte, start, mitte, temp);
			mergeSort(staedte, mitte+1, ende, temp);
			merge(staedte, start, mitte+1, ende, temp);
		}
	}
	
	public String[] merge (Knoten[] staedte, int linksPos, int rechtsPos, int rechtsEnde, String[] temp) {
		int linksEnde = rechtsPos - 1;
		int help = linksPos;
		while (linksPos <= linksEnde && rechtsPos <= rechtsEnde) {
			if (staedte[linksPos].getStadtname().compareTo(staedte[rechtsPos].getStadtname()) <= 0) {
				temp[help] = staedte[linksPos].getStadtname();
				linksPos++;
				help++;
			}
			else {
				temp[help] = staedte[rechtsPos].getStadtname();
				rechtsPos++;
				help++;
			}
		}
		while (linksPos <= linksEnde) {
			temp[help] = staedte[linksPos].getStadtname();
			linksPos++;
			help++;
		}
		while (rechtsPos <= rechtsEnde) {
			temp[help] = staedte[rechtsPos].getStadtname();
			rechtsPos++;
			help++;
		}
		return temp;

Ausgabe erscheint zwar komisch, aber ich habe mal noch das "Arrays.toString(staedte)"
durch "staedte.toString()" ersetzt, das sieht nicht ganz so grausam aus. Ausgabe ergibt folgendes:
mergeSort von 0 bis 11 auf [LKnoten;@1242719c
mergeSort von 0 bis 5 auf [LKnoten;@1242719c
mergeSort von 0 bis 2 auf [LKnoten;@1242719c
mergeSort von 0 bis 1 auf [LKnoten;@1242719c
mergeSort von 0 bis 0 auf [LKnoten;@1242719c
mergeSort von 1 bis 1 auf [LKnoten;@1242719c
merge von 0 bis 1 ende 1 auf [LKnoten;@1242719c merge von 1 bis 2 ende 1 ergibt [LKnoten;@1242719c
mergeSort von 2 bis 2 auf [LKnoten;@1242719c
merge von 0 bis 2 ende 2 auf [LKnoten;@1242719c merge von 2 bis 3 ende 2 ergibt [LKnoten;@1242719c
mergeSort von 3 bis 5 auf [LKnoten;@1242719c
mergeSort von 3 bis 4 auf [LKnoten;@1242719c
mergeSort von 3 bis 3 auf [LKnoten;@1242719c
mergeSort von 4 bis 4 auf [LKnoten;@1242719c
merge von 3 bis 4 ende 4 auf [LKnoten;@1242719c merge von 4 bis 5 ende 4 ergibt [LKnoten;@1242719c
mergeSort von 5 bis 5 auf [LKnoten;@1242719c
merge von 3 bis 5 ende 5 auf [LKnoten;@1242719c merge von 5 bis 6 ende 5 ergibt [LKnoten;@1242719c
merge von 0 bis 3 ende 5 auf [LKnoten;@1242719c merge von 3 bis 6 ende 5 ergibt [LKnoten;@1242719c
mergeSort von 6 bis 11 auf [LKnoten;@1242719c
mergeSort von 6 bis 8 auf [LKnoten;@1242719c
mergeSort von 6 bis 7 auf [LKnoten;@1242719c
mergeSort von 6 bis 6 auf [LKnoten;@1242719c
mergeSort von 7 bis 7 auf [LKnoten;@1242719c
merge von 6 bis 7 ende 7 auf [LKnoten;@1242719c merge von 7 bis 8 ende 7 ergibt [LKnoten;@1242719c
mergeSort von 8 bis 8 auf [LKnoten;@1242719c
merge von 6 bis 8 ende 8 auf [LKnoten;@1242719c merge von 8 bis 9 ende 8 ergibt [LKnoten;@1242719c
mergeSort von 9 bis 11 auf [LKnoten;@1242719c
mergeSort von 9 bis 10 auf [LKnoten;@1242719c
mergeSort von 9 bis 9 auf [LKnoten;@1242719c
mergeSort von 10 bis 10 auf [LKnoten;@1242719c
merge von 9 bis 10 ende 10 auf [LKnoten;@1242719c merge von 10 bis 11 ende 10 ergibt [LKnoten;@1242719c
mergeSort von 11 bis 11 auf [LKnoten;@1242719c
merge von 9 bis 11 ende 11 auf [LKnoten;@1242719cException in thread "main" java.lang.NullPointerException
at Graph.merge(Graph.java:89)
at Graph.mergeSort(Graph.java:79)
at Graph.mergeSort(Graph.java:78)
at Graph.mergeSort(Graph.java:78)
at Graph.mergeSort_aufruf(Graph.java:69)
at Graph.einlesen(Graph.java:173)
at Graph.main(Graph.java:182)

Und wenn ich das Feld temp mal wie am Anfang nach jedem Schritt anzeigen lasse sieht es folgendermaßen aus:
Dresden | Riesa | null | null | null | null | null | null | null | null | null | null |
Dresden | Döbeln | Riesa | null | null | null | null | null | null | null | null | null |
Dresden | Döbeln | Riesa | Chemnitz | Flöha | null | null | null | null | null | null | null |
Dresden | Döbeln | Riesa | Chemnitz | Flöha | Olbernhau | null | null | null | null | null | null |
Chemnitz | Dresden | Flöha | Olbernhau | Riesa | Döbeln | null | null | null | null | null | null |
Chemnitz | Dresden | Flöha | Olbernhau | Riesa | Döbeln | Aue | Bärenstein | null | null | null | null |
Chemnitz | Dresden | Flöha | Olbernhau | Riesa | Döbeln | Bärenstein | Aue | Schwarzenberg | null | null | null |
Chemnitz | Dresden | Flöha | Olbernhau | Riesa | Döbeln | Bärenstein | Aue | Schwarzenberg | Johangeorgenstadt | Zwickau | null |

Und danach komt die NullPointerException. Aber bis dahin läuft das eigentlich ganz gut.

danke

 

[Marco13]

Und danach komt die NullPointerException. Aber bis dahin läuft das eigentlich ganz gut.

Das ist wie bei dem Kerl, der aus dem 10. Stock fällt, und sich nach 9 Stockwerken denkt: "Och, bis jetzt war's gar nicht so schlimm..."

Die Ausagbe der Arrays ist zwar blöd um sie hier zu posten, aber könnte ja (wenn sie in der Console stehen) helfen, nachzuvollziehen, wo der Fehler liegt - also wo er auf 'null'-Einträge zugreift - der Fehler tritt ja in "Graph.merge(Graph.java:89)" auf, d.h. dort könntest du mal schauen, was dort null ist - und dann versuchen, nachzuvollziehen, warum es null ist. Evtl. hilft es auch, das ganze mit einem Array mit 4 oder 5 Städten zu testen - falls der Fehler dann auch noch auftritt.

 

[nemo86]

vielleicht hilft das:

/**
 * MergeSort-Implementierung. Angelehnt an die Implementierung in der 
 * Java-Standardbibliothek.
 */
public class MergeSort {
	
	public static void sort(int[] seq, int from, int to) {
		int[] aux = new int[to-from];
		System.arraycopy(seq, from, aux, 0, to-from);
		mergeSort(aux, seq, from, to, from);
	
	}
	
	private static void mergeSort(int[] src, int[] dest, int low, int high, int offset) {
		
		int length = high - low;
		if (length <= 1) return;
				
		
		int destLow = low;
				
		low -= offset;
		high -= offset;
		int mid = (low + high) >>> 1;
		
		mergeSort(dest, src, low, mid, -offset);
		mergeSort(dest, src, mid, high, -offset);
		
				
		// merge
		for(int k = 0, i = low, j = mid; k < length; ++k) {
			if (i >= mid || (j < high && src[j] < src[i])) {
				dest[destLow+k] = src[j++];
			} else {
				dest[destLow+k] = src[i++];
			}
		}
		
	}
}

 

[vogella]

Hallo raffi,

hier findest Du auch ein Beispiel für Mergesort Mergesort in Java

Der Artikel beinhaltet auch einen JUnit Test; wenn Du JUnit nicht kennst, kannst Du das einfach auf eine main Methode umschreieben.


Was ich Dir empfehlen kann

1.) Nutze die Implementierung von nemo86 oder von dem Artikel
2.) Nutze einen Test (JUnit oder main Method) , um die int Implmentierung zu testen ->-> dann kannst Du schon mal sicher sein ints sortieren zu können
3.) Paßt Deinen String sortierer basiered auf 1.) an
4.) schreibt Dir einen Test (JUnit oder main method) für Strings
5.) Paßt den int Sortierer an bis Dein Test durchläuft