wie es im Wiki der Mustercode von Merge gegeben worden ist, ist es zu bemerken, falls das Element in Teilliste1 kleiner als oder gleich dem Element von Teilliste2 ist, wird das Element von Teillist1 in der Hauptliste gefügt und der Index von Teilliste1 inkrementiert, falls nicht, wird dann das Element von Teilliste2 im else-Block in die Hauptliste gefügt und index von Teilliste2 inkrementiert und der Index von Teilliste1 bleibt unverändert. D.h , die Teilliste1 hat die Höhere Priorität beim Vergleichen aber Im FOO ist ganz anders und zwar falls die zu vergleichenden Elemente gleich sind, wird erst das Element von Teilliste2 in die Hauptliste hinzugefügt obwohl das Element von Teilliste1 (Laut Algorithmus im Algowiki) in die Liste hinzugefügt wird ( Im Beispiel im Foo sollen, in der 12. Iteration, Zeiger I1 = 8 und Zeiger I2 = 4 sein(Angehängtes Bild)) . Ich wollte mal fragen an welche Source ich mich eigentlich wenden soll, Algowiki oder FOO??
Im Algowiki :http://wiki.algo.informatik.tu-darmstad ... /Mergesort
public static <T> void mergesort(List<T> liste, Comparator<T> cmp) {
if (liste.size() <= 1)
return;
LinkedList<T> teilliste1 = new LinkedList<T>(); // leer
LinkedList<T> teilliste2 = new LinkedList<T>();
zerlegeInTeillisten(liste, teilliste1, teilliste2);
mergesort(teilliste1, cmp);
mergesort(teilliste2, cmp);
liste.clear();
merge(teilliste1, teilliste2, liste, cmp);
}
// -----------------
public static <T> void zerlegeInTeillisten(List<T> liste,
List<T> teilliste1, List<T> teilliste2) {
ListIterator<T> it = liste.listIterator();
for (int i = 0; i < liste.size(); i++) {
T elem = it.next();
if (i <= liste.size() / 2)
teilliste1.add(elem); // Haengt elem hinten an teilliste1 an
else
teilliste2.add(elem); // Dito teilliste2
}
}
// ---------------
public static <T> void merge(List<T> teilliste1, List<T> teilliste2,
List<T> liste, Comparator<T> cmp) {
ListIterator<T> it1 = teilliste1.listIterator();
ListIterator<T> it2 = teilliste2.listIterator();
T elem1 = it1.next();
T elem2 = it2.next();
while (true) {
if (cmp.compare(elem1, elem2) <= 0) {
liste.add(elem1);
if (!it1.hasNext())
break; // Bricht die Schleife ab, aber im Gegensatz zu
// return nicht die Methode.
elem1 = it1.next();
} else {
liste.add(elem2);
if (!it2.hasNext())
break;
elem2 = it2.next();
}
}
// Hier wissen wir: ! it1.hasNext() || ! it2.hasNext()
while (it1.hasNext())
liste.add(it1.next());
while (it2.hasNext())
liste.add(it2.next());
}
