28.3.2 Implementierung des Mergesort-Algorithmus
 
der Aufruf Wie schon beim Quicksort soll auch hier der Aufruf des Sortieralgorithmus so aussehen:

Sortieren.mertgeSort(liste);

Die Klassenmethode mergeSort muss also so aussehen:

public static void mergeSort(int[] liste){
  mergeSort(liste, new int[liste.length], 0, liste.length-1);
}
  Für den Rekursiven Abstieg muss die Signatur von mergeSort anders aussehen. Im Parameter muss noch die Information über die Grenzen der Teilliste übergeben werden. Die rekursive Methode hat also die Signatur:


 

  mergeSort(int[] liste, int[] hilfsListe,
          int
links, int rechts): void
 
Quellkode der rekursiven Methode:
 
mergeSort(...) private static void mergeSort(int[] liste, int[] hilfsListe,
                              int
links, int rechts){
  if (links<rechts){
    int mitte=(links+rechts)/2;
    mergeSort(liste, hilfsListe, links, mitte);
    mergeSort(liste, hilfsListe, mitte+1, rechts);
    merge(liste, hilfsListe, links, mitte, rechts);
  }
}
  Das wieder Zusammenmischen der Listen und das Sortieren dabei, bringen wir in einer eigenen Methode merge(...) unter.
 
merge(...)

 

 

 

 

 

 

Download:
Sortieren.java

private static void merge(int[] listeA, int[] listeB, 
                          int links, int mitte, int rechts){
  int i, j, k;


  // beide Hälften von a in Hilfsliste b kopieren
  for (i=links; i<=rechts; i++){
    listeB[i]=listeA[i];
  }
  i=links; j=mitte+1; k=links;
  // jeweils das nächstgrößte Element zurückkopieren
  while (i<=mitte && j<=rechts){
    if (listeB[i]<=listeB[j])
      listeA[k++]=listeB[i++];
    else
      listeA[k++]=listeB[j++];
  }
  // Rest zurückkopieren
  while (i<=mitte)
    listeA[k++]=listeB[i++];
}
zu 28.3.3 Übungen
zur Startseite www.pohlig.de  (C) MPohlig 2006