Java MergeSort - wie funktioniert dieses Split/Merge verfahren?

[ReVo]

Hallo,

also ich verstehe nicht genau wie das ganze Split/Merge verfahren funktionieren soll. Wir lesen wikipedia natürlich durch, vorallem die bilder gucken wir uns an, denn die sind toll (http://de.wikipedia.org/wiki/Mergesort)

Im grunde weiß ich nur dass zuerst alles in 2 hälften aufgeteilt wird und dann immer weiter kleiner und kleiner zerlegt wird.

Wie soll ich das verstehen? Am anfang mache ich 2 listen und dann 4 und dann 8?!

Dannach werden die aufgesplitteten teile wieder zusammengelegt... und dann im letzten schritt gibt es wieder nur zwei listen und die werden zusammensortiert und wir haben die sortierte liste. Da ist auch die frage, wie genau werden die zusammen gelegt...?

Also im grunde konnte ich nur den aller letzten schritt coden. Also wenn man nur noch 2 listen hat, daraus macht man dann eine fertige:

	public static void mergeSort() {
		
		int[] daten = {1,5,8,2,3,9}; //das hier soll sortiert werden
		int laenge = daten.length; //größe der zu sortierende liste
		int speicher; int mitte = 0; int i = 0; int j = 0; int k = 0;
		
		mitte = daten.length/2;

		int[] liste1 = new int[mitte];
		int[] liste2 = new int[mitte];
		int[] sortiert = new int[laenge-1];//später soll hier die sortierte liste drinne sein
		
		//Teile die unsortierte Liste in 2 Listen auf
		while(i < mitte) {
			liste1[i] = daten[i];
			i++;
		}
		
		i = mitte; j = 0;
		while(i < (laenge)) {
			liste2[j] = daten[i];
			i++;
			j++;
		}
		
		System.out.println("Liste1: "+ toString(liste1));
		System.out.println("Liste2: "+ toString(liste2));
		
		//Sortiere die zwei unsortierten Listen
		i = 0; j = 0;
		while(i < mitte) {
			
			if(liste1[i] < liste2[j]) {
				sortiert[k] = liste1[i];
				i++;
			}
			else if(liste1[i] > liste2[j]) {
				sortiert[k] = liste2[j];
				j++;
			}
			k++;
		}

		System.out.println("Sortiert: "+ toString(sortiert));
	}

Gut das klappt auch natürlich Aber das ist eigentlich nur das aller kleinste teil...

Jemand noch irgendwelche tips zum MergeSorte? Oder zum code, da ich sicher bin, dass es auch schöner zu coden geht, vorallem wenn man mit listen arbeiten möchte - bin halt noch nicht so fitt in java(aber das sieht man denke ich ^^)

Danke

 

[Bender86]

Beim zusammenmischen von zwei Listen guckst du dir immer das erste Element der beiden Listen an und hängst das kleinere davon ein deine Resultat Liste, dadurch wird beim zusammenmergen sortiert.

Also Liste A: 1,5,6 Liste B: 2,4,7:

Wird erst die 1 in die neue Liste gehängt und aus Liste A gelöscht. Dann ist die 2 aus Liste B das kleinste, erste Element, und so weiter.. dann kriegt man durchs Mergen. 1,2,4,5,6,7...

Da dieser Schritt rekursiv für alle Teillisten gemacht wird, wird die gesamte Liste sortiert.

Muss jetzt meinen Bus kriegen, kann später noch was schreiben.



/edit

Also das Sortieren passiert dadurch, dass du deine aufgeteilten Listen sortiert zusammenfügst. Wie schon beschrieben indem du in deine Resultat-Liste immer das kleinere der beiden ersten Elemente anfügst.

Da die gesamte Liste am Anfang einmal in seine einzelnen Elemente zerlegt wird und diese sortiert zusammengefügt werden, ist am Ende die gesamte Liste ebenfalls sortiert. Das ganze kann man dann ganz gut rekursiv ausdrücken, gaaanz grob so:

	public List mergeSort(List list) {
		
		if(list.length <= 1) {
			return list;
		} else {
			return merge(mergeSort(leftSide), mergeSort(rightSide));
		}
	}
	
	public List leftSide(List list) {
		// Gibt die linke Hälfte der Liste zurück
	}
	
	public List rightSide(List list) {
		// Gibt die rechte Hälfte der Liste zurück
	}
	
	public List merge(List list1, List list2) {
		List result;
		
		while(listen.nichtLeer) {
		
			if(list1.erstesElement <= list2.erstesElement) {
				
				result.add(list1.erstesElement);
				list1.remove(erstesEelement);
				
			} else {
				
				result.add(list2.erstesElement);
				list2.remove(erstesElement);
				
			}
		}
		return result;
	}

 

[ReVo]

Hi,

danke! Es hat etwas länger gedauert bis ich das richtig verstanden habe. Wichtig bei der ganzen sache ist, dass man das rekursiv macht, das hätte ich verstehen müssen.

Gruß