Kurs:Algorithmen und Datenstrukturen/Kapitel 2/MergeSort/Java

Quelltext

Eine Java-Klasse zur Implementierung des Mergesortieralgorithmus könnte folgendermaßen aussehen (Siehe auch: Aktivierung von Syntaxhighlighting):

/**
* Klasse zum Sortieren eines Arrays von sortierbaren Objekten
* mit Hilfe des Merge-Sortieralgorithmus
*/
public class MergeSort{
 
 public static void sort( final Comparable[] a ){
   /* Internes Array */
   final Comparable[] b = new Comparable[a.length];
   /* Kopie des Ausgangsarrays erzeugen */
   System.arraycopy( a,0,b,0,a.length );
   /* Sortieralgorithmus starten */
   sort( b,a,0,a.length-1 );
 }
 
 private static void sort( final Comparable[] src, final Comparable[] dest, final int von, final int bis ){
   if(bis == von){   // Ein Element ist immer sortiert
     System.arraycopy( src,von,dest,bis,1 );
   }else if(bis - von == 1){  // Zwei Elemente sind trivial zu sortieren
     if(src[bis] == null || src[von] == null){   // unzulässige Arrayelemente abfangen
       throw new IllegalArgumentException("Null-Elemente im Array sind nicht erlaubt");
     }
     if(src[bis].compareTo( src[von] )<0){
       System.arraycopy( src,von,dest,bis,1 );
       System.arraycopy( src,bis,dest,von,1 );
     }else{
       System.arraycopy( src,von,dest,von,2 );
     }
   }else if(bis - von > 1){  // mehrere Elemente zu sortieren
     final int m = von+(bis-von)/2; // Integeroverflow vermeiden
     sort( dest,src,von,m );  // linke Hälfte sortieren
     sort( dest,src,m+1,bis );  // rechte Hälfte sortieren
     /*Durchlaufe die zwei Hälften und fülle die Werte in dest */
     int i = von, j = m+1, k = von;
     while( i<=m && j<=bis){
       System.arraycopy( src,(src[i].compareTo(src[j])<0)?i++:j++,dest,k++,1 );
     }
     if(i<=m) {System.arraycopy( src,i,dest,k,m-i+1 );}
     if(j<=bis){System.arraycopy( src,j,dest,k,bis-j+1 );}
   }else{
     throw new IllegalArgumentException("bis="+bis+" ist kleiner als von="+von+"!");
   }
 }
}

Die Sortierung

Statische, öffentliche Methode sort

Die im Quelltext angegebene als public static deklarierte Methode sort( final Comparable[] a ) erwartet beim Aufruf ein Array von vergleichbaren, also sortierbaren, Objekten. Durch das für jedes Array existierende Attribut length lässt sich die Länge des Arrays zur Aufrufzeit feststellen. Dadurch kann ein internes Array namens "b" zur Aufnahme von ebenfalls length vergleichbaren Objekten vorbereitet werden. Die statische Methode arraycopy( a,0,b,0,a.length ) aus der Klasse System kopiert das übergebene Array a in das interne Array b.

Nach dieser Vorbereitung wird die interne, als private deklarierte Sortiermethode sort( b,a,0,a.length-1 ) aufgerufen, um die eigentliche Sortierung vorzunehmen. Hierbei wird der Inhalt des b-Arrays in das a-Array sortiert und zwar vom ersten bis zum letzten Element, welche in Java von Null bis Elementeanzahl minus Eins nummeriert werden.

Da die öffentliche (public) Methode statisch (static) deklariert wurde, könnte ein Aufruf folgendermaßen realisiert werden:

MergeSort.sort(zu sortierendes Array);

Statische, interne Methode sort

Die interne Sortiermethode sortiert den Inhalt des ersten Arrays src ins zweite Array dest, wobei die Elemente mit dem Index von beginnend bis zum Index bis berücksichtigt werden.

to be continued...