Mergesort: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
K (Akaibel verschob Seite Mergesort ab Abi 2017 nach Mergesort) |
|||
(3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 3: | Zeile 3: | ||
[[File:Mergesort.png|thumb|Mergesort für das Wort "informatik" |428px]] | [[File:Mergesort.png|thumb|Mergesort für das Wort "informatik" |428px]] | ||
'''<font color='red'>nicht relevant fürs Zentralabitur!</font>''' | '''<font color='red'>nicht relevant fürs Zentralabitur!</font>''' | ||
= Funktionsweise = | = Funktionsweise = | ||
Zeile 18: | Zeile 16: | ||
=Implementierung= | =Implementierung= | ||
<code> | <code> | ||
'''public List<String> mergesort(List<String> pList){''' | |||
List<String> ergebnis = new List<>(); | |||
} | List<String> links = new List<>(); | ||
List<String> rechts = new List<>(); | |||
'''// Abbruchbedingung: nur 1 Element in pList''' | |||
pList.toFirst(); | |||
pList.next(); | |||
if(pList.hasAccess() == false) { | |||
return pList; | |||
} | |||
'''// verteilen auf links und rechts''' | |||
boolean nachLinks = true; | |||
for(pList.toFirst(); pList.hasAccess(); pList.next()) { | |||
String s = pList.getContent(); | |||
if(nachLinks == true) { | |||
links.append(s); | |||
nachLinks = false; | |||
} | |||
else { | |||
rechts.append(s); | |||
nachLinks = true; | |||
} | |||
} | |||
'''//sortieren der Teillisten durch rekursive Aufrufe''' | |||
List<String> linksSortiert = '''mergesort(links);''' | |||
List<String> rechtsSortiert = '''mergesort(rechts);''' | |||
'''// die beiden sortierten Listen zu einer einzigen verschmelzen''' | |||
ergebnis = merge(linksSortiert, rechtsSortiert); | |||
return ergebnis; | |||
} | |||
</code> | |||
'''Die folgende Hilfs-Methode verschmilzt zwei sortierte Listen zu einer einzigen.''' | |||
<code> | |||
'''private List<String> merge(List<String> l1, List<String> l2) {''' | |||
<code> | List<String> ergebnis = new List<>(); | ||
l1.toFirst(); | |||
l2.toFirst(); | |||
// beide Listen parallel durchlaufen | |||
while(l1.hasAccess() && l2.hasAccess()){ | |||
private List< | // jeweils die erste String auslesen | ||
String s1 = l1.getContent(); | |||
String s2 = l2.getContent(); | |||
// die alphabetisch kleinere der beiden Strings | |||
// in die Liste ergebnis uebertragen | |||
// und in der Herkunftsliste eins weiter gehen | |||
if(s1.compareTo(s2) < 0){ | |||
ergebnis.append(s1); | |||
l1.next(); | |||
} | |||
else{ | |||
ergebnis.append(s2); | |||
l2.next(); | |||
} | |||
} | |||
// den Rest der ersten Liste (wenn es einen gibt) | |||
// in ergebnis uebertragen | |||
while(l1.hasAccess()){ | |||
ergebnis.append(l1.getContent()); | |||
l1.next(); | |||
} | |||
// den Rest der zweiten Liste (wenn es einen gibt) | |||
// in ergebnis uebertragen | |||
while(l2.hasAccess()){ | |||
ergebnis.append(l2.getContent()); | |||
l2.next(); | |||
} | |||
return ergebnis; | |||
} | } | ||
</code> | </code> |
Aktuelle Version vom 15. Dezember 2022, 17:09 Uhr
nicht relevant fürs Zentralabitur!
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
public List<String> mergesort(List<String> pList){
List<String> ergebnis = new List<>();
List<String> links = new List<>();
List<String> rechts = new List<>();
// Abbruchbedingung: nur 1 Element in pList
pList.toFirst();
pList.next();
if(pList.hasAccess() == false) {
return pList;
}
// verteilen auf links und rechts
boolean nachLinks = true;
for(pList.toFirst(); pList.hasAccess(); pList.next()) {
String s = pList.getContent();
if(nachLinks == true) {
links.append(s);
nachLinks = false;
}
else {
rechts.append(s);
nachLinks = true;
}
}
//sortieren der Teillisten durch rekursive Aufrufe
List<String> linksSortiert = mergesort(links);
List<String> rechtsSortiert = mergesort(rechts);
// die beiden sortierten Listen zu einer einzigen verschmelzen
ergebnis = merge(linksSortiert, rechtsSortiert);
return ergebnis;
}
Die folgende Hilfs-Methode verschmilzt zwei sortierte Listen zu einer einzigen.
private List<String> merge(List<String> l1, List<String> l2) {
List<String> ergebnis = new List<>();
l1.toFirst();
l2.toFirst();
// beide Listen parallel durchlaufen
while(l1.hasAccess() && l2.hasAccess()){
// jeweils die erste String auslesen
String s1 = l1.getContent();
String s2 = l2.getContent();
// die alphabetisch kleinere der beiden Strings
// in die Liste ergebnis uebertragen
// und in der Herkunftsliste eins weiter gehen
if(s1.compareTo(s2) < 0){
ergebnis.append(s1);
l1.next();
}
else{
ergebnis.append(s2);
l2.next();
}
}
// den Rest der ersten Liste (wenn es einen gibt)
// in ergebnis uebertragen
while(l1.hasAccess()){
ergebnis.append(l1.getContent());
l1.next();
}
// den Rest der zweiten Liste (wenn es einen gibt)
// in ergebnis uebertragen
while(l2.hasAccess()){
ergebnis.append(l2.getContent());
l2.next();
}
return ergebnis;
}