Sortieren durch Einfügen mit abnehmender Schrittweite (Shellsort)

Zuerst werden alle Elemente sortiert, die drei Stellen von einander entfernt sind. Als nächstes werden die Daten sortiert, die zwei Positionen von einander entfernt sind. Zuletzt werden alle benachbarten Elemente sortiert.

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

public class Shell extends Frame {
    
    int h[] = new int[101];

    public Shell() {
        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 k;
        int hilfsvar;

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

        k=1;
        do {
            k=k*3+1;
        } while (k<=100);

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

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

Durch das anfängliche Sortieren von Elementen, die weiter von einander entfernt sind, werden Elemente, die weit von ihrem Platz in der sortieren Menge entfernt liegen, rascher über längere Strecken hinweg bewegt. Dadurch erhält der Shellsort eine bedeutende Effizienz für stark ungeordnete Mengen.