/** * Kurzbeschreibung der Klasse Mergesort: * ... * @author (Ihr Name) * @version (Versions Nummer oder Datum) */ //@SuppressWarnings("unchecked"); import java.util.ArrayList; public class Mergesort extends Sortierer{ /** * Default-Konstruktor für Objekte der Klasse Mergesort */ public Mergesort(int pLaenge) { super(pLaenge); } public void sortiereZufallsliste() { super.druckeListeAufConsole(); Stoppuhr uhr = new Stoppuhr(); vergleiche = 0; vertauschungen = 0; uhr.starte(); // ----------------------------- liste = this.mergesort(liste); // ----------------------------- uhr.stoppe(); messzeit = uhr.gibMesszeit(); super.druckeListeAufConsole(); super.zeigeAuswertung(messzeit); } private ArrayList mergesort(ArrayList pListe) { if (pListe.size() > 1) { int mitte = pListe.size() / 2; ArrayList links = new ArrayList(pListe.subList(0, mitte)); ArrayList rechts = new ArrayList(pListe.subList(mitte, pListe.size())); // Rekursiver Aufruf von Mergesort auf die beiden Hälften links = mergesort(links); rechts = mergesort(rechts); // Beide Hälften wieder zusammenführen return merge(links, rechts); } else{ return pListe; } } // Methode, um zwei sortierte Listen zu einer zusammenzuführen private ArrayList merge(ArrayList pLinks, ArrayList pRechts) { ArrayList gemischt = new ArrayList(); int i = 0, j = 0; // Elemente aus beiden Listen der Größe nach hinzufügen while (i < pLinks.size() && j < pRechts.size()) { if (pLinks.get(i) <= pRechts.get(j)) { gemischt.add(pLinks.get(i)); i++; } else { gemischt.add(pRechts.get(j)); j++; } } // Restliche Elemente aus der linken Liste hinzufügen while (i < pLinks.size()) { gemischt.add(pLinks.get(i)); i++; } // Restliche Elemente aus der rechten Liste hinzufügen while (j < pRechts.size()) { gemischt.add(pRechts.get(j)); j++; } return gemischt; } } // Ende der Klasse Mergesort