QuickSort in Java mit Interfaces

interface SortObject


{ public int compare (SortObject o);

}

Wie man sieht wird der Funktionskörper von compare durch ein Semikolon ; ersetzt. Man kann nun eine beliebige Klasse sortierbar machen, wenn man compare implementiert. Wir wollen als Beispiel wieder double-Werte sortieren. Dazu schreiben wir eine neue Klasse SortDouble.



class SortDouble implements SortObject

{ private double X;

public SortDouble (double x)

{ X=x;

}

public double getValue ()

{ return X;

}

public int compare (SortObject o)

{ SortDouble s=(SortDouble)o;

if (X

else if (X==s.X) return 0;

else return 1;

}

}

Diese Klasse kann einen double-Wert aufnehmen und implementiert die compare-Methode. Nun folgt das Hauptprogramm, das eine statische Funktion Sorter.sort() aufruft. Die Klasse Sorter enthält eine entsprechende Routine, die den Quicksort-Algorithmus implementiert. Diese Methode bekommt ein Array aus Instanzen von SortObject übergeben. Da SortDouble dieses Interface implementiert, geht auch ein Array aus SortDouble.



public class Test

{ public static void main (String args[])

{ int i,n=1000;



// Get an array of random numbers:

SortDouble x[]=new SortDouble[n];

for (i=0; i



// Sort it:

Sorter.sort(x);



// Test, if the order is correct:

for (i=1; i

if (x[i].getValue()

System.out.println("Fehler beim Sortieren");

}

}

Die Methode Sorter.sort weiß nun nichts von double-Werten, sondern benutzt nur compare aus dem Interface SortObject.



class Sorter

{ static public void sort (SortObject v[])

{ QuickSort(v,0,v.length-1);

}



static private void QuickSort

(SortObject a[], int lo0, int hi0)

{ int lo=lo0;

int hi=hi0;

SortObject mid;



if (hi0>lo0)

{ mid = a[(lo0+hi0)/2];

while(lo<=hi)

{ while((lo

++lo;

while((hi>lo0) && (a[hi].compare(mid)>0))

--hi;

if(lo<=hi)

{ swap(a,lo,hi);

++lo;

--hi;

}

}

if(lo0

if(lo

}

}



static private void swap (SortObject a[], int i, int j)

{ SortObject T;

T=a[i];

a[i]=a[j];

a[j]=T;

}

}