Seite 1 von 1

Merge Algorithm im FOO

Verfasst: 28. Mai 2015 14:27
von sch3rvv1n
Hello allerseits,

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());
}

Re: Merge Algorithm im FOO

Verfasst: 28. Mai 2015 19:40
von luedecke
Das liegt wohlmöglich daran, dass die Methode merge() dort nichts zu suchen hat.
Die aktuelle Version der Spezifikation von merge selbst ist neuer als dieser Code. Demnach ist diese Methode veraltet und passt nicht auf den Rest.
Video und foo haben die entsprechende Correctness.

Ich werde die Methode nun aus dem Wiki entfernen.