Probleme bei codierung von MergeSort

[PhiRie]

Hallo,

ich muss in meiner Übungsaufgabe den Sortieralgorithmus MergeSort codieren. Dabei bekomme ich immer eine Index out of Bounds Fehlermeldung!

Die Aufgabenstellung lautet dabei wie folgt:

• man kopiere sich die beiden Teillisten in die Hilfs-Felder a1 und a2
• man verwende Index-Pointer i=0 für a1, j=0 für a2, und k=l für a
• solange kein Index-Pointer i,j das Ende erreicht hat vergleicht man a1 und a2[j] und kopiert den kleineren Wert nach a[k] dann ist k und entweder i oder j um 1 zu erhöhen
  [*]Rest der Teillisten die noch nicht vollständig abgearbeitet ist an a anzuhängen
  

Ich habe schon länger gegoogelt und auch die Forensuche habe ich benutzt, aber nichts hilft mir wirklich weiter. Ich gebe zu die rekursion von mergeSort ebenfalls nicht voll verstanden zu haben, vielleicht kommt daher auch mein Problem.

Ich benutze Eclipse als CASE-Tool und habe auch den Debugger schon ausprobiert, aber da ich diesen noch nie verwendet habe ist das alles nicht so hilfreich.

Ich hoffe ihr könnt mir helfen und da es mein erster Beitrag ist hoffe ich euch auch alle Informationen gegeben zu haben. Deshalb hier mal die Fehlermeldung und meine Methoden. Danke schon mal im vorraus...

9 8 7 6 5 4 3 2 1
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 9
at meinPaket.SortSearch.merge(SortSearch.java:199)
at meinPaket.SortSearch.mergeSort(SortSearch.java:152)
at meinPaket.SortSearch.mergeSort(SortSearch.java:150)
at meinPaket.SortSearch.mergeSort(SortSearch.java:151)
at meinPaket.SortSearch.mergeSort(SortSearch.java:150)
at meinPaket.SortSearch.main(SortSearch.java:18)


Methode mergeSort war bereits vorgegeben:

public static void mergeSort(int[] a, int l, int r){
		
		if(l<r){
			
			int m = (r+l)/2;
			mergeSort(a, l, m);
			mergeSort(a, m+1, r);
			merge(a, l, m, r);
			
		}
	}

Hier meine fehlerhafte Methode merge:

public static void merge(int[] a, int l, int m, int r){
	
		int[] a1 = new int[(a.length+1)/2];
		int[] a2 = new int[(a.length+1)/2];
		
		for(int k=l; k <= m; k++) {
			
			a1[k] = a[k];
		}
			
		for(int k=m+1; k < r; k++) {
			
			a2[k-(m+1)] = a[k];
		}
		
		int k = l;
		int i = 0;
		int j = 0;
			
		while(i < a1.length && j < a2.length){
			
			if(a1[i]<=a2[j]){
				
				a[k++]=a1[i++];
				
			}else{
				
				a[k++]=a2[j++];
			}
		}
		
		if(i<m){
			
			while(i<m){
				
				a[k++]=a1[i++];
			}
		}
		if(j<r){
			
			while(j<m){
				
				a[k++]=a2[j++];
			}
		}
		
		
		
	}

Hier noch der Aufruf:

public static void main(String[] args){
		
		
		int[] test2 = {9,8,7,6,5,4,3,2,1};
		printArray(test2);
		System.out.println();
		mergeSort(test2, 0, 10);
		printArray(test2);
		
	}

 

[SlaterB]

einfach anschauen was das Programm macht und mit deinem Konzept vergleichen, welches du hoffentlich hast,

System.out.println("merge: " + l + ", " + m + ", " + r + ", Arrays: " + a1.length + ", " + a2.length);
recht nah zu Beginn von merge() zeigt locker leicht, dass als letztes vor der Exception gemergt wird mit l, m, r gleich 3, 3, 4,
also nur 2 Felder im Array,
die Teil-Arrays haben immer Länge 5,

> while(i < a1.length && j < a2.length)
sieht da schon übel aus,

und die Exception findet in diesem Fall letztlich in der letzten while-Schleife statt, while (j < m),
warum läuft dort der Index j beginnend bei 0 bis m=3? das sind allein 4 Indexe, obwohl es doch nur um 2 Felder geht


erstmal auf Papier aufmalen, was in der Situation l, m, r gleich 3, 3, 4 überhaupt passieren soll,
was kommt in die TeilArrays, wo laufen die Indexe i und j?


zur Vereinfachung kannst du auch erstmal mit Arrays der Länge 2 oder 3 anfangen, da gibts auch schon teils andere Exceptions,

einfaches Spiel:
immer mit System.out.println oder einem Debugger nachschauen, WAS passiert,
und dies mit dem geplanten Ablauf vergleichen

 

[PhiRie]

Ja genau hier liegt ja ein Teil meines Problems, da ich das ganze nicht zeichnen kann da ich nicht kapiere wie der Ablauf der rekursiven Methode mergeSort ist.

1. Aufruf: m=4 berechnet. Unterer Teil: 0 bis 4. Oberer Teil 5 bis 9
....
beim Letzten Aufruf habe ich das Array dann in 9 einzelne Zahlen zerlegt und die werden der Methode merge übergeben welche diese auf Größe überprüft und dann wieder zusammenfügt???

ich kapier das einfach nicht..

 

[SlaterB]

wie willst du etwas programmieren, was du nicht verstehst?
dann wäre dein Code dazu obsolet,

erst musst du das Verfahren kennenlernen,
Mergesort ? Wikipedia
und manuell an einem Beispiel durchspielen können

das Bild dort

muss dir etwas sagen, dazu brauchst du eine merge-Methode bei der du den Inhalt und Sinn jeder Variablen kennst usw.,
blindes Versuchen führt zu nix


versuche es vielleicht lieber wirklich erstmal mit jeder Menge neuer Arrays,
bevor du den effizienteren Weg, innerhalb des einen Original-Arrays an bestimmten Positionen Werte zu ersetzen, angehst

 

[PhiRie]

Zur vollständigkeit, hab jetzt die Lösung:

	public static void merge(int[] a, int l, int m, int r){
	
		int[] a1 = new int[m-l+1];
		int[] a2 = new int[r -m ];
		
		for(int k=0; k < m-l+1; k++) {
			
			a1[k] = a[l+k];
		}
			
		for(int k=0; k < r-m; k++) {
			
			a2[k] = a[m+1+k];

		}
		
		int k = l;
		int i = 0;
		int j = 0;
			
		while(i < a1.length && j < a2.length){
			
			if(a1[i]<=a2[j]){
				
				a[k++]=a1[i++];
				
			}else{
				
				a[k++]=a2[j++];
			}
		}
		
		if(i<a1.length){
			
			while(i<a1.length){
				
				a[k++]=a1[i++];
			}
		}else{
		
			
			while(j<a2.length){
				
				a[k++]=a2[j++];
			}
		}
		
		
		
	}