Sortieren durch Austauschen (Bubblesort)

Obwohl dieses Sortierverfahren zu den ungünstigsten zählt, wird es häufig angeführt. Das Datenfeld wird bei $n$ Daten immer $(n-1)$ mal durch laufen: 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.

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

public class Bubble extends Frame {

    int h[] = new int[101];

    public Bubble() {
        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 hilfsvar;

        g.setColor(Color.white);
        g.fillRect(5,0,500,120);
        g.setColor(Color.black);

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

        for (i=2;i<=100;i++) {
            for (j=100;j>=i; j--) {
                for (int pause=0;pause<100000;pause++) {}
                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,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]);
                }
            }
        }
    }

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

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.