Merge Algorithm im FOO

sch3rvv1n
Erstie
Erstie
Beiträge: 17
Registriert: 22. Apr 2015 10:58

Merge Algorithm im FOO

Beitrag 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());
}
Dateianhänge
Bildschirmfoto 2015-05-28 um 14.26.53.PNG
Bildschirmfoto 2015-05-28 um 14.26.53.PNG (74.59 KiB) 369 mal betrachtet

Benutzeravatar
luedecke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 17. Mär 2015 00:08

Re: Merge Algorithm im FOO

Beitrag 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.

Antworten

Zurück zu „Archiv“