Mergesort: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(2 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>'''
<font color='red'>'''Die Schnittstellenbeschreibung entspricht dem Abi 17 (und folgenden)'''</font>


= Funktionsweise =
= Funktionsweise =
Zeile 18: Zeile 16:
=Implementierung=  
=Implementierung=  
<code>
<code>
  private List<Person> teile(List<Person> pList){
  '''public List<String> mergesort(List<String> pList){'''
    '''//TODO'''  
  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> 


public List<Person> mergeSort(List<Person> pList){
'''Die folgende Hilfs-Methode verschmilzt zwei sortierte Listen zu einer einzigen.'''
    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;
}
</code>


mergeSort ruft die Methode verschmelzen auf:
<code>   
 
  '''private List<String> merge(List<String> l1, List<String> l2) {'''
<code>
  List<String> ergebnis = new List<>();
  /**
  l1.toFirst();
  * verschmilzt zwei sortierte Listen
  l2.toFirst();
  * zu einer sortierten Liste
  // beide Listen parallel durchlaufen
  */
  while(l1.hasAccess() && l2.hasAccess()){
  private List<Person> verschmelzen(List<Person> l1, List<Person> l2) {
      // jeweils die erste String auslesen
    List<Person> ergebnis = new List<>();
      String s1 = l1.getContent();
    l1.toFirst();
      String s2 = l2.getContent();
    l2.toFirst();
      // die alphabetisch kleinere der beiden Strings
    // beide Listen parallel durchlaufen
      // in die Liste ergebnis uebertragen
    while(l1.hasAccess() && l2.hasAccess()){
      // und in der Herkunftsliste eins weiter gehen
      // jeweils die erste Person auslesen
      if(s1.compareTo(s2) < 0){
      Person p1 = l1.getContent();
        ergebnis.append(s1);
      Person p2 = l2.getContent();
        l1.next();
      // die alphabetisch kleinere der beiden Personen
      }
      // in die Liste ergebnis uebertragen
      else{
      // und aus der Herkunftsliste loeschen
        ergebnis.append(s2);
      if(p1.getName().compareTo(p2.getName()) < 0){
        l2.next();
    ergebnis.append(p1);
      }
    l1.remove();
  }
      }
  // den Rest der ersten Liste (wenn es einen gibt)
      else{
  // in ergebnis uebertragen
    ergebnis.append(p2);
  while(l1.hasAccess()){
    l2.remove();
      ergebnis.append(l1.getContent());
      }
      l1.next();
    }
  }
    // den Rest der ersten Liste (wenn es einen gibt)
  // den Rest der zweiten Liste (wenn es einen gibt)
    // in ergebnis uebertragen
  // in ergebnis uebertragen
    while(l1.hasAccess()){
  while(l2.hasAccess()){
      ergebnis.append(l1.getContent());
      ergebnis.append(l2.getContent());
      l1.remove();
      l2.next();
    }
  }
    // den Rest der zweiten Liste (wenn es einen gibt)
  return ergebnis;
    // in ergebnis uebertragen
    while(l2.hasAccess()){
      ergebnis.append(l2.getContent());
      l2.remove();
    }
    return ergebnis;
  }
  }
</code>
</code>

Aktuelle Version vom 15. Dezember 2022, 17:09 Uhr


Mergesort für das Wort "informatik"

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