Sortieren durch Einfügen

Man wählt ein Element nach dem anderen und fügt es jeweils an die richtige Stelle der bereits geordneten Liste ein. Dabei ist allerdings eine Reihe von Tauschvorgängen notwendig, weil beim Einfügen andere Elemente jeweils um eine Position nachrücken müssen.

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

public class Einfuegen extends Frame {

    int h[] = new int[101];

    public Einfuegen() {
        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++) {
            hilfsvar=h[i];
            j=i-1;
            while ((hilfsvar<h[j]) && (j>0)) {
                h[j+1]=h[j];
                g.setColor(Color.white);
                g.fillRect(j*5,20,3,100);
                g.fillRect((j+1)*5,20,3,100);
                g.setColor(Color.black);
                g.fillRect((j+1)*5,120-h[j],3,h[j]);
                j--;
                g.setColor(Color.black);
                g.fillRect((j+1)*5,120-hilfsvar,3,hilfsvar);
                for (int pause=0;pause<100000;pause++) {}
            }
            h[j+1]=hilfsvar;
        }
    }

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

In diesem Beispiel wurde die grafische Ausgabe anders realisiert als im Beispiel vorher. Im Beispiel zur Minimumsuche wurden alle Zahlen des Arrays nach jedem Tauschvorgang als Rechtecke neu dargestellt. Im Beispiel zum Sortieren durch Einfügen werden nur die beiden Rechtecke der beiden vertauschten Zahlen neu gezeichnet. Dabei werden zuerst zwei Rechtecke in der Hintergrundfarbe Color.white gezeichnet und dann die neuen Rechtecke in der Farbe Color.black neu dargestellt.