Java - 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 gegeben...

Beispiel:

Code:

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

public class shaker 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 paint (Graphics g) {
	int i;
	int j;
	int l;
	int r;
	int k;
	int hilfsvar;

	g.setColor(Color.white);
       	g.fillRect(0,0,500,100);
	g.setColor(Color.black);
	for (l=1;l<=100;l++) {
	    g.fillRect(l*5,100-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,0,5,100);
		    g.fillRect(j*5,0,5,100);
		    g.setColor(Color.black);
		    g.fillRect((j-1)*5,100-h[j-1],3,h[j-1]);
		    g.fillRect(j*5,100-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,0,5,100);
		    g.fillRect(j*5,0,5,100);
		    g.setColor(Color.black);
		    g.fillRect((j-1)*5,100-h[j-1],3,h[j-1]);
		    g.fillRect(j*5,100-h[j],3,h[j]);
		}		
	    }
	    r=k-1;
	} while (l<=r);
    }
}

Kommentar:

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