Sortier­verfahren

Shellsort

 Inhalt  English version  aufwärts

Shellsort ist eines der am längsten bekannten Sortier­verfahren (benannt nach seinem Urheber D.L. Shell [She 59]). Es ist sehr schnell, einfach zu verstehen und einfach zu implementieren, allerdings ist seine Analyse etwas aufwendiger.

 

Idee

Die Idee des Verfahrens ist, die Daten als zwei­dimensionales Feld zu arrangieren und spaltenweise zu sortieren. Dadurch wird eine Grobsortierung bewirkt. Dann werden die Daten als schmaleres zwei­dimensionales Feld angeordnet und wiederum spaltenweise sortiert. Dann wird das Feld wiederum schmaler gemacht usw. Zum Schluss besteht das Feld nur noch aus einer Spalte.

Werden die Feldbreiten geschickt gewählt, reichen jedesmal wenige Sortier­schritte aus, um die Daten spaltenweise zu sortieren bzw. am Ende, wenn nur noch eine Spalte vorhanden ist, vollständig zu sortieren. Die Effizienz von Shellsort hängt von der Folge der gewählten Feldbreiten ab.

Beispiel:  Sei 3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2 die zu sortierende Datenfolge. Als erstes werden die Daten als Feld mit 7 Spalten arrangiert (links), anschließend werden die Spalten sortiert (rechts):

3790516
8420615
734982
 
 
 Pfeil 
 
3320515
7440616
879982

Hierdurch sind die Elemente 8 und 9 schon an das Ende der Datenfolge gelangt; allerdings steht auch noch ein sehr kleines Element (die 2) dort. Im nächsten Schritt werden die Daten in 3 Spalten angeordnet, die wiederum sortiert werden:

332
051
574
406
168
799
82
 
 
 
 
 Pfeil 
 
001
122
334
456
568
779
89

Jetzt sind die Daten bereits fast vollständig sortiert. Wenn die Daten anschließend in einer Spalte angeordnet werden, müssen lediglich noch eine 6, eine 8 und eine 9 etwas weiter nach unten sortiert werden.

 

Implementierung

Tatsächlich werden die Daten nicht in unter­schiedlich breite Felder umarrangiert, sondern die Daten stehen in einem ein­dimensionalen Feld, das entsprechend indiziert wird. Beispielsweise bilden die Elemente an den Index­positionen 0, 5, 10, 15 usw. die erste Spalte eines 5-spaltigen Feldes. Die durch die jeweilige Indizierung entstehenden "Spalten" werden im Shellsort-Algorithmus mittels Insertionsort sortiert, da Insertionsort bei teilweise vorsortierten Daten recht effizient ist.

Die folgende Funktion shellsort sortiert ein Array a beginnend beim Index 0 bis zum Index n-1. Die Anzahl der Spalten, in die die Daten jeweils arrangiert werden, ist im Array cols angegeben. Zuerst werden die Daten also in 1391376 Spalten angeordnet (sofern so viele Daten vorhanden sind), zum Schluss in einer Spalte. Diese im Array cols befindlichen Werte sind entscheidend für die Zeitkomplexität von Shellsort – es dürfen nicht zu viele Werte sein, damit nicht zu viele Iterationen zustande kommen, und die Werte müssen sorgfältig aufeinander abgestimmt sein, damit pro Iteration möglichst wenig Sortier­schritte erforderlich sind. Eine entsprechende Analyse folgt im Anschluss an den Algorithmus. Die hier verwendeten Werte stammen von Sedgewick [Sed 96].

Jede Spalte wird mit Insertionsort sortiert. Zuerst werden die Daten der zweiten Zeile (diese beginnt bei i = h) in ihren jeweiligen Spalten einsortiert, dann die Daten der dritten Zeile (wenn i den Wert 2h erreicht) usw.

Die Sortier­funktion ist in der Klasse ShellSorter gekapselt. Die Methode sort übergibt das zu sortierende Array an das Array a, setzt n auf dessen Länge und ruft shellsort auf.

Mit den Anweisungen

ShellSorter s=new ShellSorter();
s.sort(b);

wird ein Objekt vom Typ ShellSorter angelegt und anschließend die Methode sort zum Sortieren eines Arrays b aufgerufen. Es folgt das Programm.

 

public class ShellSorter
{
    private int[] a;
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        shellsort();
    }

    private void shellsort()
    {
        int i, j, k, h, t;
        int[] cols = {1391376, 463792, 198768, 86961, 33936,
          13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1};

        for (k=0; k<16; k++)
        {
            h=cols[k];
            for (i=h; i<n; i++)
            {
                j=i;
                t=a[j];
                while (j>=h && a[j-h]>t)
                {
                    a[j]=a[j-h];
                    j=j-h;
                }
                a[j]=t;
            }
        }
    }

}    // end class ShellSorter

 

Analyse

Die Korrektheit des Verfahrens ist gesichert, da im letzten Schritt (mit h = 1) ein normales Insertionsort auf der gesamten Folge durchgeführt wird. Durch die vorherigen Schritte (h = 3, 7, 21, ...) sind die Daten jedoch bereits so vorsortiert, dass wenige Insertionsort-Schritte ausreichen. Wie viele genau, ist Gegenstand der folgenden eingehenden Analyse. Ausschlag­gebende Bedeutung hat hierbei die Folge der Feldbreiten (im Folgenden als h-Folge bezeichnet).

Grundlagen

Ein Brief kostet 16F Porto, eine Postkarte 11F. Es sind nur Briefmarken zu 3F und zu 7F vorhanden. Ist es möglich, den Brief bzw. die Postkarte exakt zu frankieren?

Offenbar besteht das Problem darin, die Zahlen 16 bzw. 11 jeweils als Linear­kombination k·3 + l·7 mit ganzzahligen, nichtnegativen Koeffizienten k, l darzustellen. Welche natürlichen Zahlen lassen sich aus Vielfachen von 3 und 7 kombinieren und welche nicht?

Definition:  Seien g, h Element natürliche Zahlen. Wir nennen eine Zahl f eine Kombination von g und h, wenn sich f als Linear­kombination f = kg + lh mit Koeffizienten k, l Element natürliche Zahlen0 darstellen lässt.

Beispiel:  Es gilt 16 = 3·3 + 1·7, damit ist 16 eine Kombination von 3 und 7. Der Brief kann also exakt frankiert werden.

Definition:  Seien g, h Element natürliche Zahlen teilerfremd. Wir bezeichnen mit N(g, h) die (endliche) Menge der natürlichen Zahlen, die keine Kombinationen von g und h sind und mit γ(g, h) die größte dieser Zahlen:

N(g, h)  =  { f Element natürliche Zahlen  |  ¬ es existiert k, l Element natürliche Zahlen0f = kg + lh },

γ(g, h)  =  max(N(g, h)).

Beispiel:  Seien g = 3, h = 7. Dann ist

N(g, h)  =  {1, 2, 4, 5, 8, 11}   und

γ(g, h)  =  11.

Satz:  Sind g, h Element natürliche Zahlen teilerfremd, so gilt:

γ(g, h)  =  (g-1)·(h-1) – 1,

d.h. jede natürliche Zahl f mit fgrößer gleich(g-1)·(h-1) ist eine Kombination von g und h.

h-Sortierung

Definition:  Sei h Element natürliche Zahlen. Eine Folge a0, ..., an-1 heißt h-sortiert, wenn für alle i Element {0, ..., n-1-h} gilt

aikleiner gleichai+h.

Eine h-sortierte Folge entsteht, wenn die Folge zeilenweise in ein Feld mit h Spalten geschrieben wird und die Spalten sortiert werden. Eine 1-sortierte Folge ist sortiert.

Satz:  Seien g, h Element natürliche Zahlen. Eine g-sortierte Folge bleibt g-sortiert, wenn sie h-sortiert wird.

Beweis:   Pfeil Beweis

Definition:  Eine Folge, die g-sortiert und h-sortiert ist, nennen wir g,h-sortiert.

Satz:  Eine g,h-sortierte Folge ist g+h-sortiert.

Beweis:  Sei a = a0, ..., an-1 die g,h-sortierte Folge. Es ist zu zeigen, dass für alle i Element {0, ..., n-1-(g+h)} gilt:

aikleiner gleichai+g+h.

Dies ist aber der Fall, denn aikleiner gleichai+g, weil die Folge g-sortiert ist und ai+gkleiner gleichai+g+h, weil die Folge h-sortiert ist.

Hieraus folgt sofort der folgende Satz.

Satz:  Ist eine Folge g,h-sortiert, dann ist sie (kg+lh)-sortiert für alle k, l Element natürliche Zahlen0, d.h. die Folge ist f-sortiert für alle f, die Kombinationen von g und h sind.

Satz:  Sei a eine g,h-sortierte Folge, wobei g und h teilerfremd sind. Für beliebige Elemente ai und aj, die einen Abstand j – i von mindestens (g-1)·(h-1) haben, gilt:

aikleiner gleichaj.

Beweis:  Sei f = j – i. Ist fgrößer gleich(g-1)·(h-1), so ist f Kombination von g und h, damit ist die Folge f-sortiert, also gilt

aikleiner gleichai+f = aj.

Der Satz besagt also, dass in einer g,h-sortierten Folge, wobei g und h teilerfremd sind, rechts von jedem Element ai kleinere Elemente nur innerhalb der nächsten (g-1)·(h-1) – 1 Positionen vorkommen können; die darauf folgenden Elemente sind alle größer oder gleich ai.

Behauptung:  Sei a = a0, ..., an-1 eine g,h-sortierte Folge, wobei g und h teilerfremd sind, sei ferner d eine Variable. Liegen sowohl g als auch h in O(d), so genügen O(n·d) Sortier­schritte, um die Folge d-sortiert zu machen.

Beweis:  Nach Aussage des vorigen Satzes befinden sich rechts von jedem Element ai kleinere Elemente nur innerhalb der nächsten (g-1)·(h-1) – 1 Positionen.

Wird die Folge jetzt d-sortiert, so kommt in der Spalte unter ai nur jedes d-te dieser maximal (g-1)·(h-1) – 1 kleineren Elemente vor. Unter jedem ai (i = 0, ..., n-1) stehen also maximal (g-1)·(h-1)/d kleinere Elemente, mit denen ai vertauscht werden muss. Somit werden maximal n·(g-1)·(h-1)/d Schritte für die d-Sortierung benötigt.

Da sowohl g als auch h in O(d) liegen, sind dies O(n·d) Schritte.

Hieraus lassen sich obere Schranken für die Anzahl der Sortier­schritte von Shellsort gewinnen.

Obere Schranken

Satz:  Mit der h-Folge 1, 3, 7, 15, 31, 63, 127, ..., 2k – 1, ... benötigt Shellsort O(n·Wurzeln) Schritte, um eine Datenfolge der Länge n zu sortieren  (Papernov und Stasevic [PS 65]).

Beweis:  Sei ht dasjenige Element der h-Folge, das am nächsten bei Wurzeln liegt. Wir analysieren das Verhalten von Shellsort getrennt für die Elemente hk mit kkleiner gleicht und für die Elemente hk mit k > t.

Sei kkleiner gleicht. Da hk = 2k – 1 ist, sind hk+1 und hk+2 teilerfremd und liegen in O(hk). Daher genügen O(n·hk) Sortier­schritte, um die Datenfolge hk-sortiert zu machen.

Da die hk eine geometrische Reihe bilden, liegt die Summe aller hk mit k = 1, ..., t in O(ht) = O(Wurzeln). Damit werden insgesamt O(n·Wurzeln) Sortier­schritte für diesen Teil des Algorithmus benötigt.

 

Sei nun k > t. Wenn die Daten in einem Feld mit hk Spalten arrangiert werden, enthält jede Spalte n/hk Elemente. Es werden daher O((n/hk)2) Sortier­schritte pro Spalte benötigt, da Insertionsort quadratische Komplexität hat. Es gibt hk Spalten, dies führt insgesamt zu O((n/hk)2·hk) = O(n·n/hk) Sortier­schritten für die hk-Sortierung der gesamten Datenfolge.

Wiederum bilden die n/hk eine geometrische Reihe, deren Summe in O(n/ht) = O(Wurzeln) liegt. Somit sind für k > t ebenfalls O(n·Wurzeln) Sortier­schritte erforderlich, so dass sich insgesamt die obere Schranke von O(n·Wurzeln) ergibt.

Es kann gezeigt werden, dass mit dieser Folge die obere Schranke im schlechtesten Fall auch erreicht wird. Es gibt aber andere h-Folgen, die zu einem effizienteren Verhalten von Shellsort führen.

Satz:  Mit der h-Folge 1, 2, 3, 4, 6, 8, 9, 12, 16, ...,  2p3q, ... benötigt Shellsort O(n·log(n)2) Schritte, um eine Datenfolge der Länge n zu sortieren  (Pratt [Pra 79]).

Beweis:  Ist g = 2 und h = 3, so ist γ(g, h) = (g-1)·(h-1) – 1 = 1, d.h. in einer 2,3-sortierte Folge kann jedes Element höchstens ein kleineres Element unmittelbar rechts von sich stehen haben. Es genügen daher n Sortier­schritte, um die Datenfolge zu sortieren.

Betrachtet man Elemente mit geradem und mit ungeradem Index getrennt, so wird klar, dass ebenfalls n Sortier­schritte genügen, um eine 4,6-sortierte Folge 2-sortiert zu machen. Analog dazu genügen n Sortier­schritte, um eine 6,9-sortierte Folge 3-sortiert zu machen.

Die obige h-Folge ist so konstruiert, dass zu jedem hk auch 2hk und 3hk vorkommen. Insgesamt sind dies log(n)2 Elemente; für jedes hk genügen n Sortier­schritte, somit ergibt sich eine Komplexität von O(n log(n)2).

Die h-Folge von Pratt liefert zwar asymptotisch das beste Ergebnis, sie besteht jedoch aus relativ vielen, nämlich log(n)2 Elementen. Insbesondere bei Daten, die bereits vorsortiert sind, sind h-Folgen mit weniger Elementen besser, da die Daten ja pro Element einmal durchlaufen werden müssen, auch wenn nur wenige Sortier­schritte ausgeführt werden.

Durch Kombination der Argumente aus diesen beiden Sätzen lassen sich h-Folgen mit O(log(n)) Elementen gewinnen, die in der Praxis zu sehr guten Ergebnissen führen, so etwa die h-Folge von Sedgewick aus dem angegebenen Programm [Sed 96]. Allerdings scheint es keine h-Folge zu geben, mit der Shellsort eine Komplexität von O(n log(n)) erreicht (siehe [Sed 96]). Möglicherweise gibt es jedoch h-Folgen, mit der diese Komplexität im Durchschnitt erreichbar ist.

 

Sortiernetz

Durch Verwendung von Bubblesort anstelle des daten­abhängigen Insertionsort lässt sich Shellsort auch als Sortiernetz implementieren. Mit der h-Folge 2p3q besteht es aus Θ(n·log(n)2) Vergleichern. Das folgende Bild 1 zeigt ein entsprechendes Sortiernetz für n = 8.

Shellsort-Sortiernetz für n = 8
Bild 1:  Shellsort-Sortiernetz für n = 8

 

Visualisierung

 

(Java-Applet zur Visualisierung von Shellsort)

 

Literatur

[Knu 73]D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)
[Pra 79]V. Pratt: Shellsort and Sorting Networks. Garland, New York (1979)
[PS 65]A. Papernov, G. Stasevic: A Method of Information Sorting in Computer Memories. Problems of Information Transmission 1, 63-75 (1965)
[Sed 88]R. Sedgewick: Algorithms. 2. Auflage, Addison-Wesley (1988)
[Sed 96]R. Sedgewick: Analysis of Shellsort and Related Algorithms. In: Josep Díaz, Maria Serna (Eds.): Algorithms - ESA '96, Fourth Annual European Symposium, Barcelona, Lecture Notes in Computer Science, Vol. 1136, Springer, 1-11 (1996)
[She 59]D.L. Shell: A High-Speed Sorting Procedure. Communications of the ACM, 2, 7, 30-32 (1959)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Shellsort und andere Sortier­verfahren, so etwa Quicksort, Heapsort und Mergesort, finden Sie auch in meinem Buch über Algorithmen.
Weiterevertikaler Abstand Themen des Buches: Textsuche, Graphenalgorithmen, algorithmische Geometrie, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

 

Weiter mit:   [Untere Schranken für das Sortieren]   oder   up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 29.01.1998   Updated: 01.03.2014
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnik

Wirtschaftsinformatik