Java - Sortieren durch Austauschen (Bubblesort)

Obwohl dieses Sortierverfahren zu den ungünstigsten zählt, wird es häufig dargestellt. Das Datenfeld wird immer (n - 1) mal durchlaufen (wobei n die Anzahl der zu sortierenden Daten ist): Jedesmal werden benachbarte Elemente in die richtige Reihenfolge vertauscht - die Datenreihe ist sortiert, wenn kein Austausch mehr notwendig ist. Obwohl die Zahl der Vergleiche und die Zahl der eventuell notwendigen Tauschvorgänge bei jedem Durchlauf um 1 abnimmt, ist dieses Verfahren vor allem bei »ungünstig« sortierten Ausgangsdaten sehr langsam.

Beispiel:

Code:

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

public class bubble 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 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]);
	}

	for (i=2;i<=100;i++) {
	    for (j=100; j>=i; j--) {
		for (int k=1;k<100000;k++) {}
		if (h[j-1]>h[j]) {
		    hilfsvar = h[j];
		    h[j] = h[j-1];
		    h[j-1] = hilfsvar;
		    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]);
		}
	    }
	}
    }
}

Kommentar:

Der Algorithmus erhält seinen Namen offenbar von der Tatsache, dass die Elemente - ähnlich wie Blasen in einem Glas Mineralwasser - aufsteigen, bis sie an der richtigen Stelle sind.