Mergesort verstehen

[Devin]

Hallo,

ich versuche gerade einen Mergesort Algorithmus in der Implementierung zu verstehen. Ein Teil des Codes war vorgegeben und daher verstehe ich ihn nicht so ganz. In der merge-Methode verstehe ich die dritte while-Schleife einfach nicht. In der ersten while-Schleife wird ein Hilfsarray b gefüllt mit den Werten des Arrays, die sich links der Mitte befinden. In der zweiten wird das Hilfsarray verglichen mit den Werten rechts des Arrays.

In der dritten while-Schleife (while (k<j)...)komme ich jedoch nicht weiter und wollte daher fragen, ob mir da jemand erklären kann, was dort gemacht wird und was der Sinn dieser Schleife ist.


[CODE lang="java" title="Mergesort"]public class MergeSort {
private int []a = {1,8,7,9,6,5,3,2,4};
public MergeSort(){
mergesort(0,a.length-1);
this.Ausgeben();
}
public void mergesort(int links, int rechts)
{
if (links<rechts){
int m= (links+rechts)/2;//m steht für die Mitte des Arrays
mergesort(links, m);// Hier wird die linke Hälfte des Arrays in einzelne Elemente aufgeteilt
mergesort(m+1,rechts);// Hier wird die rechte Hälfte des Arrays in einzelne Elemente aufgeteilt
merge(links,m,rechts);
}
}
public void merge(int links, int mitte, int rechts){
int i, j ,k;
i = 0;
j = links;
int []b = new int[mitte-links+1];//soll ein Hilfsarray sein
while(j <= mitte){
//Die while-Schleife soll das Hilfsarray füllen mit Werten, die links von der Mitte stehen
b=a[j];
i++;
j++;
}
i = 0;
k = links;
while(k < j && j <= rechts){
//Die Zahlen links der Mitte und die Zahlen rechts der Mitte werden miteinnder verglichen.
if(b <= a[j]){
a[k]=b;
//a[k] ist das "Gesamtarray"
k++;
i++;
}else{
a[k]=a[j];
k++;
j++;
}
}
while(k < j){
a[k]=b;
k++;
i++;
}
}
public void Ausgeben(){
for (int i=0;i<a.length;i++)
System.out.print(a);

System.out.println("");
}

}[/CODE]

 

[mihe7]

Was ist denn die Aufgabe von merge? Die Methode soll zwei bereits sortierte Teile eines Arrays sortiert zusammenführen. Mal Dir einfach ein Array auf und geh den Spaß schrittweise durch, dann wirst Du relativ schnell feststellen, welche Aufgabe in welcher Schleife übernommen wird - und warum.

EDIT: solltest Du wirklich nicht draufkommen, melde Dich einfach nochmal.

 

[Kirby.exe]

Also im Grunde ist es recht simpel Du hast, wie @mihe7 bereits gesagt hat, zwei Arrays. Das mergen beginnt in der untersten Rekursionsstufe. Somit hast du im ersten Merge zwei "einelementige" Arrays. Nun hast du zwei Pointer k und j mit welchen du von vorne nach hinten durch deine Arrays gehst. Sprich du vergleichst immer die beiden Elemente an Index k und j. Dies machst du in der "großen" While schleife solange bis eines deiner Arrays abgearbeitet ist. In den anderen beiden Schleifen prüfst du ob das betrachtete Array leer ist oder nicht.

Sollte dieses leer sein, dann wird die Schleife nicht durchlaufen. Somit handelst du mit einer letzten beiden Schleifen die restlichen Elemente im anderen nicht-leeren Array ab

 

[Blender3D]

In der dritten while-Schleife (while (k<j)...)komme ich jedoch nicht weiter und wollte daher fragen, ob mir da jemand erklären kann, was dort gemacht wird und was der Sinn dieser Schleife ist.

Wikipedia erklärt es Dir
https://de.wikipedia.org/wiki/Mergesort#Implementierung