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

Beispiel:

Code:

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

public class shell 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 k;
	int hilfsvar;

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

Kommentar:

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