Kurs:Algorithmen und Datenstrukturen/Kapitel 2/MergeSort/Java
Quelltext
BearbeitenEine 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
classMergeSort
{public
static
voidsort
( 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
voidsort
( final Comparable[] src, final Comparable[] dest, final int von, final int bis ){ if(bis == von){ // Ein Element ist immer sortiertSystem
.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 thrownew 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 sortierenfinal
intm
= von+(bis-von)/2; // Integeroverflow vermeidensort
( dest,src,von,m ); // linke Hälfte sortierensort
( dest,src,m+1,bis ); // rechte Hälfte sortieren /*Durchlaufe die zwei Hälften und fülle die Werte in dest */ inti
= 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{ thrownew IllegalArgumentException
("bis="+bis+" ist kleiner als von="+von+"!"); } } }
Die Sortierung
BearbeitenStatische, öffentliche Methode sort
BearbeitenDie 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
BearbeitenDie 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...