Shellsort

Shellsort

Shellsort ist ein von Donald L. Shell im Jahre 1959 entwickeltes Sortierverfahren, das auf dem Sortierverfahren des direkten Einfügens (Insertionsort) basiert.

Inhaltsverzeichnis

Prinzip

Shellsort bedient sich prinzipiell des Insertionsorts. Es versucht den Nachteil auszugleichen, dass hier Elemente in der Sequenz oft über weite Strecken verschoben werden müssen. Dies macht Insertionsort ineffizient. Shellsort verfolgt den Ansatz, dass die Sequenz z.B. erst 4-sortiert wird, dann 2-sortiert, und zuletzt mit normalem Insertionsort sozusagen 1-sortiert.

Anschaulich wäre dies anhand von Hilfsmatrizen darzustellen (siehe Beispiel):

  • Die Daten werden in eine k-spaltige Matrix zeilenweise geschrieben
  • Die Spalten der Matrix werden einzeln sortiert

Daraus resultiert eine grobe Sortierung. Dieser Schritt wird mehrmals wiederholt, wobei jeweils die Breite der Matrix verringert wird, bis die Matrix nur noch aus einer einzigen vollständig sortierten Spalte besteht.

Shellsort arbeitet in-place, gehört jedoch nicht zu den stabilen Sortieralgorithmen.

Beispiel

Zu sortieren sind die Zahlen 2, 5, 3, 4, 3, 9, 3, 2, 5, 4, 1, 3 mittels der Folge 2n,...,4,2,1

Zuerst werden die Daten in eine Matrix mit vier Spalten eingetragen und spaltenweise sortiert. Die Zahlenfolge wird also 4-sortiert.

2 5 3 4      2 4 1 2
3 9 3 2  →   3 5 3 3
5 4 1 3      5 9 3 4

Die sortierte Vier-Spalten-Matrix wird nun in zwei Spalten aufgeteilt, wobei von links nach rechts gelesen wird. Diese Spalten werden nun 2-sortiert.

2 4      1 2
1 2      2 3
3 5  →   3 4
3 3      3 4
5 9      3 5
3 4      5 9

Die sortierte Zwei-Spalten-Matrix wird nun in eine Spalte geschrieben und wieder sortiert mittels normalem Insertionsort. Der Vorteil dabei besteht darin, dass kein Element der Sequenz so weit verschoben werden muss, wie beim Insertionsort, der auf eine nicht vorsortierte Folge angewendet wird.

1 2 2 3 3 4 3 4 3 5 5 9  →   1 2 2 3 3 3 3 4 4 5 5 9

Die hier verwendete Schrittfolge 1,2,4,8,16,...,2n (wie es 1959 original von Shell vorgeschlagen wurde) erweist sich in der Praxis allerdings als nicht zweckmäßig, da nur gerade Stellen sortiert werden und ungerade Stellen der Sequenz nur im letzten Schritt angefasst werden. Als zweckmäßiger hat sich 1,4,13,40, ... erwiesen (Wertn = 3×Wertn-1+1).

Implementierung

Java 5

Shellsort ist eine Verbesserung des Algorithmus straight insertion. Dort wandern nämlich die Elemente in Einzelschritten auf ihren Platz: Nach dem Finden des kleinsten Elements werden die dazwischenliegenden einzeln hochgeschoben und nur das kleinste „springt“. Die meisten (d.h. n) Elemente werden von ihrem ursprünglichen Platz in durchschnittlich n/3 Schritten zu ihrem endgültigen Platz geschoben.

Beim Shell-Sort führt man abnehmende Schrittweiten k[1], k[2], … k[t] ein, wobei die letzte Schrittweite immer k[t] = 1 ist. Es werden nacheinander t Schritte durchgeführt; im m-ten Schritt springen die Elemente in Richtung ihres zukünftigen Platzes um jeweils k[m] Stellen. Im ersten Schritt werden diejenigen Elemente untereinander sortiert, die k[1] Stellen voneinander entfernt sind; dann diejenigen, die eine Entfernung k[2] voneinander haben usw. Der Effekt dieser Vorgehensweise ist es, dass die Elemente im ersten Durchgang nicht um einen, sondern um k[1] Stellen zu ihrem Platz „springen“.

Die letzte Schrittweite k[t] ist 1, d.h. zum Schluss wird ein ganz normaler Sortiervorgang straight insertion durchgeführt. Dies garantiert, dass am Ende die Reihung sortiert ist. Der Algorithmus braucht jedoch kaum noch etwas zu tun, da die vorherigen Schritte die Reihung schon fast vollständig sortiert haben.

Durch die geeignete Wahl der Schrittweiten k[1], k[2], … k[t] kann der Sortieraufwand deutlich reduziert werden. Für die Schrittweiten (1, 3, 7, 15, 31, … ) wurde nachgewiesen (s. Donald E. Knuth: The Art of Computer Programming), dass die Zeitkomplexität des Algorithmus n hoch 1,2 beträgt, was deutlich besser ist, als die quadratische Komplexität von Bubblesort, Insertionsort oder Selectionsort, jedoch (zumindest für sehr große Datenmengen) schlechter als die Komplexität n log n von Quicksort oder Heapsort.

 static <E extends Comparable<? super E>> void shellSort(E[] sammlung, int[] schrittweiten) {
   for (int schrittweite : schrittweiten) { // straight insertion mit schrittweite
      for (int index = schrittweite; index < sammlung.length; index++){
         E elementZumEinfuegen = sammlung[index];
         int einfuegestelle = index;
         while (einfuegestelle - schrittweite >= 0 && 
               elementZumEinfuegen.compareTo(sammlung[einfuegestelle-schrittweite]) < 0) {
            sammlung[einfuegestelle] = sammlung[einfuegestelle - schrittweite];
            einfuegestelle -= schrittweite; // Sprung um schrittweite
         }
         sammlung[einfuegestelle] = elementZumEinfuegen;
      }
   }
 }

Java

Tatsächlich werden die Daten nicht in Form einer Matrix, sondern in Form eines eindimensionalen Feldes angeordnet. Die Spalten werden durch geschickte Indizierung gebildet. So bilden alle Elemente im Abstand h eine Spalte. Die Spalten werden per Insertionsort sortiert, da dieser Algorithmus von einer Vorsortierung der Daten profitieren kann.

In folgendem Programm werden die Daten zuerst in h=2147483647 Spalten angeordnet, sofern so viele Daten vorhanden sind. Wenn nicht, wird die for-i-Schleife übersprungen und mit h=1131376761 fortgefahren usw.

void shellsort (int[] a, int n)
{ 
    int i, j, k, h, t;
 
    int[] spalten = {2147483647, 1131376761, 410151271, 157840433,
    58548857, 21521774, 8810089, 3501671, 1355339, 543749, 213331,
    84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1};
 
    for (k=0; k<23; k++)
    { 
        h=spalten[k];
        // Sortiere die "Spalten" mit Insertionsort
        for (i=h; i<n; i++)
        { 
            t=a[i];
            j=i;
            while (j>=h && a[j-h]>t)
            { 
                a[j]=a[j-h];
                j=j-h;
            }
            a[j]=t;
        }
    }
}

Komplexität und Distanzfolgen

Die Komplexität von Shellsort hängt von der Wahl der Distanzfolge für die Spaltenanzahl h ab. Für verschiedene Folgen sind Obergrenzen der Komplexität bewiesen worden, die damit einen Anhaltspunkt für die Laufzeit geben. Die meisten theoretischen Arbeiten über die Folgen betrachten nur die Anzahl Vergleiche als wesentlichen Kostenfaktor. Doch in realen Implementierungen zeigt sich, dass auch die Schleifen und Kopieraktionen bei nicht riesigen Arrays eine entscheidende Rolle spielen.

Ursprünglich schlug Donald Shell die Folge 1, 2, 4, 8, 16, 32, ..., 2k vor. Die Performance ist allerdings sehr schlecht, weil erst im allerletzten Schritt die Elemente auf ungeraden Positionen sortiert werden. Die Komplexität ist mit  \mathcal{O}(n^{2}) sehr hoch.

Mit der Folge 1, 3, 7, 15, 31, 63, ..., 2k - 1 von Hibbard wird eine Komplexität von  \mathcal{O}(n^{1,5}) erreicht.

Mit der Folge 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2p3q von Pratt ist die Komplexität  \mathcal{O}(n \cdot \log (n)^2) .

Donald Knuth hat auch einige Folgen für Shellsort erarbeitet. Eine häufig in der Literatur verwendete ist folgende: 1, 4, 13, 40, 121, 364, 1093, ..., (3k-1)/2. Bekannter ist die Berechnungsvorschrift der selben Folge: 3hk-1 + 1. Die Komplexität ist  \mathcal{O}(n^{1,5}) .

Einige gute Folgen stammen von Robert Sedgewick. Die Folge 1, 8, 23, 77, 281, 1073, 4193, 16577, ..., 4k+1 + 3*2k + 1 hat Komplexität von  \mathcal{O}(n^{4/3}) erreicht. Eine wesentlich bessere Folge ist folgende: 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, ..., 9*2k - 9*2k/2 + 1 (k gerade) bzw. 8*2k - 6*2(k+1)/2 + 1 (k ungerade)

Betrachtet man rein geometrische Folgen, so liegt ein Minimum in der größeren Umgebung von Faktor 2,3, d.h. die Folgeglieder haben das Verhältnis von ungefähr 2,3. Eine der theoretisch besten Folgen (d.h. Zahl der Vergleiche), die experimentell ermittelt wurde von Marcin Ciura ist 1, 4, 10, 23, 57, 132, 301, 701, 1750 und basiert auf diesen Faktor. Basierend auf den Faktor 1750/701 wird die Reihe wie folgt fortgesetzt: sei g das letzte Glied, dann ist das nächste durch 1+floor(2,5*g) gegeben, also 701, 1753, 4383, 10958, 27396, 68491, 171228, ... Eine Folge von Gonnet und Baeza-Yates basiert auf den Faktor 2,2, die sehr gute Ergebnisse liefert.

Erstaunlicherweise sind in der Praxis bessere Folgen als die von Marcin Ciura bekannt, die sich rekursiv berechnen. Der Laufzeit des Shellsort ist kürzer, obwohl die Zahl der Vergleiche höher ist (zu sortierende Elemente sind Ganzzahlen in Registerbreite). Rekursive Folgen berechnen sich aus Ganzzahlen und das Verhältnis der Folgeglieder konvergiert gegen einen bestimmten Wert, bei den Fibonaccizahlen ist es der Goldener Schnitt.

Eine solche Folge basiert auf den Fibonaccizahlen. Eine der beiden 1er am Anfang wird weggelassen und jede Zahl der Folge mir mit dem Doppelten des Goldener Schnitt (ca. 3,236) potenziert, was dann zu dieser Distanzfolge führt: 1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, ...

Eine andere rekursive Folge wurde von Matthias Fuchs gefunden. Die Folge 1, 4, 13, 40, 124, 385, 1195, 3709, 11512, 35731, ... hat als Konvergenzwert ungefähr 3.103803402. Die Berechnungsvorschrift ist fk+1 = 3*fk + fk-2, wobei die Folge initial mit 1, 1, 1 startet und für den Shellsort werden die ersten beiden 1er weggelassen.

Andere Folgen sind nicht konstant, sondern werden aus der aktuellen Anzahl von Elementen im Array berechnet. Initialisiert werden sie mit dieser Anzahl und sinken ab bis sie schließlich bei 1 angekommen sind.
Robert Kruse: hk-1 = hk/3 + 1
Gonnet und Baeza-Yates: hk-1 = (5*hk - 1) / 11 Beide Folgen habe eine etwas schlechtere Performance als die beiden rekursiven Folgen und die sehr gute Folgen von Sedgwick und die von Marcin Ciura. Aber sie sind direkt in den Shellsort-Algorithmus integrierbar.

Die Existenz einer Folge mit der Komplexität  \mathcal{O}(n \cdot \log (n)) wurde bereits ausgeschlossen in einer Arbeit von Poonen, Plaxton, und Suel. Doch konnte bewiesen werden, dass prinzipiell für hinreichend großes n immer eine Folge mit einer Komplexität von  \mathcal{O}(n^{1+e}) gefunden werden kann.

Die Suche nach einer optimalen Folge gestaltet sich dabei als äußerst schwierig. Zu große Abstände zwischen den Folgegliedern ergeben zu große Verschiebungen, zu enge Abstände bewirken zu viele Durchläufe bis zur letztendlichen Sortierung. Dabei gilt es bei der Wahl einer Folge zu vermeiden, dass zwei aufeinanderfolgende Glieder der Folge gemeinsame Teiler haben, da eine a*b-sortierte Folge auch a-sortiert und b-sortiert ist, sodass es dann zu unnützen Sortierschritt käme. Über mehrere Glieder hinweg ist das durchaus von Vorteil.

Ein wesentlicher Vorteil des Shellsort-Algorithmus im Vergleich zu anderen liegt darin, dass er bereits vorhandene Sortierungen ausnutzen kann. Dabei spielt es nur eine geringe Rolle, ob das Array sortiert oder invers sortiert vorliegt. Beide Fälle sind um Faktoren schneller als ein rein zufällig sortiertes Array. Bei nur 65536 ist der Geschwindigkeitsvorteil ca. Faktor 4, bei 128 immerhin noch mehr als Faktor 2.

Variationen

Combsort arbeitet ähnlich wie Shellsort. Dabei wird die Spaltensortierung nur mit einem Durchlauf von Bubblesort sortiert, bevor die Spaltenanzahl verringert wird.

Literatur

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Shell sort — is a sorting algorithm that is a generalization of insertion sort, with two observations: *insertion sort is efficient if the input is almost sorted , and *insertion sort is typically inefficient because it moves values just one position at a… …   Wikipedia

  • Сортировка Шелла — (англ. Shell sort)  алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными… …   Википедия

  • Donald L. Shell — (* 1. März 1924 in Croswell, Michigan) ist ein US amerikanischer Ingenieur und Informatiker. Seine bekannteste Leistung ist das von ihm vorgeschlagene Sortierverfahren Shellsort. Leben Nach einer schnell durchlaufenen Schullaufbahn ging er an die …   Deutsch Wikipedia

  • Einfügesort — Insertionsort (engl. insertion – das Einfügen, sort – sortieren) ist ein einfaches stabiles Sortierverfahren. Es ist weit weniger effizient als andere anspruchsvollere Sortierverfahren. Dafür hat es jedoch folgende Vorteile: Es ist einfach zu… …   Deutsch Wikipedia

  • Insertion Sort — Insertionsort (engl. insertion – das Einfügen, sort – sortieren) ist ein einfaches stabiles Sortierverfahren. Es ist weit weniger effizient als andere anspruchsvollere Sortierverfahren. Dafür hat es jedoch folgende Vorteile: Es ist einfach zu… …   Deutsch Wikipedia

  • Insertion sort — Insertionsort (engl. insertion – das Einfügen, sort – sortieren) ist ein einfaches stabiles Sortierverfahren. Es ist weit weniger effizient als andere anspruchsvollere Sortierverfahren. Dafür hat es jedoch folgende Vorteile: Es ist einfach zu… …   Deutsch Wikipedia

  • Insertsort — Insertionsort (engl. insertion – das Einfügen, sort – sortieren) ist ein einfaches stabiles Sortierverfahren. Es ist weit weniger effizient als andere anspruchsvollere Sortierverfahren. Dafür hat es jedoch folgende Vorteile: Es ist einfach zu… …   Deutsch Wikipedia

  • Sortieralgorithmen — Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten… …   Deutsch Wikipedia

  • Sortieralgorithmus — Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z. B. die lexikographische Ordnung von Zeichenketten… …   Deutsch Wikipedia

  • Stabil (Sortierverfahren) — Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt. Wenn beispielsweise eine Liste alphabetisch sortierter Personendateien nach dem Geburtsdatum neu sortiert… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”