Sortieren durch Rekursion (Quicksort)

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

Das Grundprinzip dieses Sortierungsverfahrens wird in der Literatur 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 rekursviv wiederholt, bis die Datei sortiert ist.

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

public class Quick extends Frame {
    
    int h[] = new int[101];
   
    public Quick() {
        int i;
        Random r = new Random();
        for (i=1; i<=100; i++) {
            h[i] = (int) (r.nextDouble()*80);
        }
    }

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

        for (long 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,20,5,100);
                g.fillRect(j*5,20,5,100);
                hilfsvar=h[i];
                h[i]=h[j];
                h[j]=hilfsvar;
                g.setColor(Color.black);
                g.fillRect(i*5,120-h[i],3,h[i]);
                g.fillRect(j*5,120-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,520,120);
        g.setColor(Color.black);
        for (int l=0;l<=100;l++) {
            g.fillRect(l*5,120-h[l],3,h[l]);
        }
        sortiere(this, 1,100);
    }

    public static void main (String [] args) {
        ...
    }
}

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