Java - Sortieren durch Rekursion (Quicksort)

Der - wahrscheinlich - am häufigsten verwendete Sor-tieralgorithmus wurde 1960 von C.A.R.Hoare entwickelt und vorgestellt. Er ist noch leistungsfähiger als der Shellsort; allerdings arbeitet er rekursiv.

Das Grundprinzip des Sortierverfahrens wird oft als »teile und herrsche« beschrieben. Ein Datenarray wird einfach in zwei Teile zerlegt und schließlich in ihren beiden Teilen sortiert. Dies wird rekursiv implementiert: Die allgemeine Prozedur wählt einen Vergleichswert und zerlegt dann das Feld in zwei Teile, die jeweils alle Elemente enthalten, die entweder größer oder gleich dem Vergleichswert auf einer Seite und alle kleiner als der Vergleichswert auf der anderen Seite sind. Dieser Vorgang wird für beide entstandenen Teile rekursiv wiederholt, bis die Datei sortiert ist.

Beispiel:

Code:

import java.awt.*;
import java.util.Random;

public class quick extends java.applet.Applet {
    
    int h[] = new int[101];
   
    public void init() {
	int i;
	Random r = new Random();
	for (i=1; i<=100; i++) {
	    h[i] = (int) (r.nextDouble()*100);
	}
    }

    public void sortiere(Container ct, int l, int r) {
	int i;
	int j;
	int k;
	int eintrag;
	int hilfsvar;

	for (int pause=0;pause<100000;pause++) {}

	Graphics g = ct.getGraphics();
	i=l;
	j=r;
	eintrag = h[(int)((l+r)/2)];
	do {
	    while (h[i]<eintrag) {
		i++;
	    }
	    while (eintrag<h[j]) {
		j--;
	    }
	    if (i<=j) {
		g.setColor(Color.white);
		g.fillRect(i*5,0,5,100);
		g.fillRect(j*5,0,5,100);
		hilfsvar=h[i];
		h[i]=h[j];
		h[j]=hilfsvar;
		g.setColor(Color.black);
		g.fillRect(i*5,100-h[i],3,h[i]);
		g.fillRect(j*5,100-h[j],3,h[j]);
		i++;
		j--;
	    }
	} while (i<=j);
	if (l<j) sortiere(ct, l, j);
	if (r>i) sortiere(ct, i, r);
    }

    public void paint (Graphics g) {

	g.setColor(Color.white);
	g.fillRect(0,0,500,100);
	g.setColor(Color.black);
	for (int l=0;l<=100;l++) {
	    g.fillRect(l*5,100-h[l],3,h[l]);
	}
	sortiere(this, 1,100);
    }
}

Kommentar:

Wegen des rekursiven Aufrufes muss die Referenz auf das Graphik-Objekt mit einem sogenannten Container-objekt realisiert werden. Das Schlüsselwort this referenziert korrekt das Graphikobjekt Graphics g.