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