Sortieren durch Austauschen - Shakersort

Der Shakersort stellt eine geringfügige Verbesserung des Bubblesorts dar: Um weit von der richtigen Stelle liegende Elemente schneller einzusortieren, wird nach jedem Durchlauf die Laufrichtung umgekehrt. Die ``schüttelnde'' Bewegung des Verfahrens hat dem Algorithmus wohl seinen Namen verliehen...

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

public class Shaker extends Frame {

    int h[] = new int[101];

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

    public void paint (Graphics g) {
        int i;
        int j;
        int l;
        int r;
        int k;
        int hilfsvar;

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

        l=2;
        r=100;
        k=100;

        do {
            for (j=r;j>=l;j--) {
                for (int pause=1;pause<100000;pause++) {}
                if (h[j-1]>h[j]) {
                    hilfsvar=h[j-1];
                    h[j-1]=h[j];
                    h[j]=hilfsvar;
                    k=j;
                    g.setColor(Color.white);
                    g.fillRect((j-1)*5,20,5,100);
                    g.fillRect(j*5,20,5,100);
                    g.setColor(Color.black);
                    g.fillRect((j-1)*5,120-h[j-1],3,h[j-1]);
                    g.fillRect(j*5,120-h[j],3,h[j]);
                }
            }
            l=k+1;
            for (j=l;j<=r;j++) {
                for (int pause=1;pause<100000;pause++) {}
                if (h[j-1]>h[j]) {
                    hilfsvar=h[j-1];
                    h[j-1]=h[j];
                    h[j]=hilfsvar;
                    k=j;
                    g.setColor(Color.white);
                    g.fillRect((j-1)*5,20,5,100);
                    g.fillRect(j*5,20,5,100);
                    g.setColor(Color.black);
                    g.fillRect((j-1)*5,120-h[j-1],3,h[j-1]);
                    g.fillRect(j*5,120-h[j],3,h[j]);
                }               
            }
            r=k-1;
        } while (l<=r);
    }

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

Das Sortieren durch Austauschen ist jedenfalls ungünstiger als das Sortieren durch Einfügen und schlechter als das Sortieren durch Auswählen.