Mergesort
Version vom 12. September 2016, 14:19 Uhr von Akaibel (Diskussion | Beiträge) (Akaibel verschob Seite Mergesort ab Abi 2017 nach Mergesort)
nicht relevant fürs Zentralabitur!
Die Schnittstellenbeschreibung entspricht dem Abi 17 (und folgenden)
Funktionsweise
Mergesort ist ein Divide&Conquer-Verfahren.
Im Divide wird die Liste in zwei gleich große Teile aufgeteilt (wenn die Anzahl der Elemente ungerade ist, dann natürlich nicht ganz gleich groß...).
Beim Conquer werden die sortierten Teillisten zusammengefügt. Durch geschickte Implementierung kann man das in O(n) Zeit bewerkstelligen.
Laufzeit
Mergesort hat auch im Worst Case eine Laufzeit von O(n*log(n)).
Für Arrays ist allerdings Quicksort schneller, weil man bei Mergesort ständig neue Arrays erzeugen muss - bei Quicksort dagegen kann man in situ (bzw. in place) arbeiten.
Implementierung
private List<Person> teile(List<Person> pList){
//TODO
}
public List<Person> mergeSort(List<Person> pList){
List<Person> ergebnis = new List<>();
List<Person> hintereListe = new List<>();
// abbruchbedingung: nur 1 element in pList
pList.toLast();
Person hinten = pList.getContent();
pList.toFirst();
Person vorne = pList.getContent();
if(vorne == hinten)
{
// pList enthaelt nur ein Element!
return pList;
}
hintereListe = teile (pList);
//sortieren der Teillisten durch rekursiven Aufruf
List<Person> pListSortiert = mergeSort(pList);
List<Person> hintersteListSortiert = mergeSort(hintereListe);
// verschmelzen
ergebnis = verschmelzen(pListSortiert, hintersteListSortiert);
System.out.println("ende von mergesort:");
return ergebnis;
}
mergeSort ruft die Methode verschmelzen auf:
/**
* verschmilzt zwei sortierte Listen
* zu einer sortierten Liste
*/
private List<Person> verschmelzen(List<Person> l1, List<Person> l2) {
List<Person> ergebnis = new List<>();
l1.toFirst();
l2.toFirst();
// beide Listen parallel durchlaufen
while(l1.hasAccess() && l2.hasAccess()){
// jeweils die erste Person auslesen
Person p1 = (Person) l1.getContent();
Person p2 = (Person) l2.getContent();
// die alphabetisch kleinere der beiden Personen
// in die Liste ergebnis uebertragen
// und aus der Herkunftsliste loeschen
if(p1.getName().compareTo(p2.getName()) < 0){
ergebnis.append(p1);
l1.remove();
}
else{
ergebnis.append(p2);
l2.remove();
}
}
// den Rest der ersten Liste (wenn es einen gibt)
// in ergebnis uebertragen
while(l1.hasAccess()){
ergebnis.append(l1.getContent());
l1.remove();
}
// den Rest der zweiten Liste (wenn es einen gibt)
// in ergebnis uebertragen
while(l2.hasAccess()){
ergebnis.append(l2.getContent());
l2.remove();
}
return ergebnis;
}