Mergesort: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
(Die Seite wurde neu angelegt: „Kategorie:Sortierverfahren thumb|Mergesort für das Wort "informatik" |428px '''<font color='red'>nicht relevant fürs Zentralabitu…“)
 
Zeile 16: Zeile 16:
=Implementierung=  
=Implementierung=  
<code>
<code>
  private List teile(List pList){
  private List<Person> teile(List<Person> pList){
     '''//TODO'''  
     '''//TODO'''  
  }
  }
Zeile 23: Zeile 23:
     List<Person> ergebnis = new List<>();
     List<Person> ergebnis = new List<>();
     List<Person> hintereListe = new List<>();
     List<Person> hintereListe = new List<>();
 
     // abbruchbedingung: nur 1 element in pList
     // abbruchbedingung: nur 1 element in pList
     pList.toLast();
     pList.toLast();
Zeile 34: Zeile 34:
       return pList;
       return pList;
     }
     }
 
     hintereListe = teile (pList);
     hintereListe = teile (pList);
   
   
Zeile 40: Zeile 40:
     List<Person> pListSortiert = mergeSort(pList);
     List<Person> pListSortiert = mergeSort(pList);
     List<Person> hintersteListSortiert = mergeSort(hintereListe);
     List<Person> hintersteListSortiert = mergeSort(hintereListe);
 
     // verschmelzen
     // verschmelzen
     ergebnis = verschmelzen(pListSortiert, hintersteListSortiert);
     ergebnis = verschmelzen(pListSortiert, hintersteListSortiert);
Zeile 79: Zeile 79:
     // in ergebnis uebertragen
     // in ergebnis uebertragen
     while(l1.hasAccess()){
     while(l1.hasAccess()){
       ergebnis.append(l1.getObject());
       ergebnis.append(l1.getContent());
       l1.remove();
       l1.remove();
     }
     }
Zeile 85: Zeile 85:
     // in ergebnis uebertragen
     // in ergebnis uebertragen
     while(l2.hasAccess()){
     while(l2.hasAccess()){
       ergebnis.append(l2.getObject());
       ergebnis.append(l2.getContent());
       l2.remove();
       l2.remove();
     }
     }

Version vom 9. August 2016, 08:23 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

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