Skip to main content

One post tagged with "datastructures"

View All Tags

· 14 min read

Donald Shell stellt 1959 in [📖She59] einen Sortieralgorithmus vor, der später nach ihm benannt wird: Shellsort.
Die in dem Algorithmus verwendete Sortiermethode ist auch bekannt als Sortieren mit abnehmenden Inkrementen [📖OW17b, p. 88], das Verfahren ist eine Variation von Insertion Sort:

[Shellsort] uses insertion sort on periodic subarrays of the input to produce a faster sorting algorithm. [📖CL22, p. 48]

In der vorliegenden Implementierung (siehe Listing 1) werden t=log2(n)t = log_2(n) Inkremente1 hth_t2 der Form n2i\lfloor {\frac{n}{2^i}} \rfloor verwendet, um lg(n)lg(n) hh-sortierte Folgen zu erzeugen. Im letzten Schritt sortiert der Algorithmus dann in h1h_1 die Schlüssel mit Abstand=11.

Die Effizienz des Sortierverfahrens ist stark abhängig von hh: So zeigt Knuth, dass O(n32)O(n^{\frac{3}{2}}) gilt, wenn für hh gilt: hs=2s+11h_s = 2^{s+1} - 1 mit 0s<t=lg(n)0 \leq s < t = \lfloor{lg(n)} \rfloor (vgl. [📖Knu97c, p. 91]3. In unserem Fall können wir von O(n2)O(n^2) ausgehen.

Anzahl der Aufrufe für Feldvergleiche

Gesucht ist die Anzahl der zwischen zwei Feldelementen gemachte Vergleiche für große randomisierte Felder. Wir vermuten hierfür einen Wert zwischen O(n lg n)O(n\ lg\ n) und O(n2)O(n^2),

Um die Aufrufe der Feldvergleiche zu zählen, kann wie in Listing 1 eine Zählvariable c3c3 eingesetzt wird, die jeden Aufruf über ein increment protokolliert.

Listing 1: Zur Protokollierung der Aufrufe können in dem Code Zählvariablen eingesetzt werden (c1, ... ,c4).
while (distanz > 0) {
c1++;
for (i = distanz; i < feld.length; i++) {
j = i - distanz;
c2++;
while (j >= 0) {
c3++;
if (feld[j] > feld[j + distanz]) {
c4++;
swap(feld, j, j+distanz);
j = j - distanz;
} else {
j =-1;
}
}
}
distanz = distanz / 2;
}

Zur Bestimmung von c3c3 können randomisierte Felder erzeugt werden, wie es der Test-Code in Listing 2 demonstriert. Dann wird überprüft, in welchen Bereichen sich c3c3 bewegt. Da jeder auf Vergleichsoperationen basierende Sortieralgorithmus zu der Laufzeitklasse Ω(n log n)\Omega(n\ log\ n) gehört, kann im Mittel c3n log nc3 \geq n\ log\ n angenommen werden:

Jedes allgemeine Sortierverfahren benötigt zum Sortieren von N verschiedenen Schlüsseln sowohl im schlechtesten Fall als auch im Mittel wenigstens Ω(N log N)\Omega(N\ log\ N) Schlüsselvergleiche.

[📖OW17b, p. 154]

Allerdings wird n1.3n^{1.3} ab n=982n=982 schneller wachsen als n log nn\ log\ n (siehe Abbildung 1), was in der Auswertung berücksichtigt werden muss. Sonst könnte man fälschlicherweise folgern, das in dem geg. Fall die Laufzeit im Durchschnitt n log nn\ log\ n beträgt.

Listing 2: Code zum Erzeugen randomisierter Felder zum Testen von Shellsort.
int epochs = 2000;
while(epochs-- >= 0) {
int[] tests = new int[]{10, 100, 1000, 100_000, 1_000_000};
java.util.Random r = new java.util.Random();
for (int i = 0; i < tests.length; i++) {
int l = tests[i];
int[] arr = new int[l];

for (int j = l; j > 0; j--) {
arr[l - j] = r.nextInt(l + 1);
}

ShellSort.sort(Arrays.copyOfRange(arr, 0, arr.length));
}
}
info

Mit einem Wert von 100100 für die Epochen und einer Feldgröße von 2.000.0002.000.000 liefert der Test in Listing 2 folgende Ausgabe:

nlgn<n1.3<x<n2:74nlgn < n^{1.3} < x < n^2: 74
nlgn<x<n1.3:26nlgn < x < n^{1.3}: 26

Figure 1 Ab n=982 wächst n(4/3) schneller al n log n.

Wegen Ω(n log n)\Omega(n\ log\ n) interessieren wir uns für die Intervalle:

  • n log nc3n1.3n\ log\ n \leq c3 \leq n^{1.3}

  • n log nn1.3c3n2n\ log\ n \leq n^{1.3} \leq c3 \leq n^2

Die Ausführung des Tests zeigt, dass die Aufrufanzahl von c3c3 bei großen nn unterhalb n1.3n^{1.3} oder zwischen n1.3n^{1.3} und n2n^2 liegt:

It appears that the time required to sort nn elements is proportional to n1.226n^{1.226}.4 [📖She59, p. 31]

Laufzeitanalyse

Für die nachfolgenden Betrachtungen sei eine Eingabegröße n=2pn = 2^p gegeben. Die Inkremente hh entsprechen der über die Implementierung vorgegebenen Folge hh mit

ht=n2,ht1=n4,,h1=1h_t = \frac{n}{2}, h_{t-1} = \frac{n}{4}, \dots, h_1 = 1

Für die Analyse ist die Shellsort-Implementierung in Listing 3 gegeben.

Listing 3: Implementierung des Shellsort-Algorithmus.
public static int[] sort(int[] arr) {

int n = arr.length;
int delta = n/2;
int min;
int j;

while (delta > 0) { // c1

for (int i = delta; i < arr.length; i++) {

// c2

min = arr[i];
j = i;

while (j - delta >= 0 && min < arr[j - delta]) {

// c3;

arr[j] = arr[j - delta];
j -= delta;
}
arr[j] = min;
}

delta = delta / 2;

}
return arr;
}

Im Folgenden betrachten wir die Anzahl für die im Code durch Kommentare markierten Stellen c1c1 in Zeile 8, c2c2 in Zeile 12 und c3c3 in Zeile 19.

Für eine erste worst-case-Analyse ist ein Feld der Länge 1616 gegeben, in absteigender Reihenfolge sortiert (s. Abbildung 2):

Figure 2 Die für die Laufzeitabschätzung verwendete Eingabefolge 16..1.

Ganz offensichtlich gilt für c3, dass es lg(n)lg(n)-mal aufgerufen wird5. c2 befindet sich im Block der durch die in Zeile 11 definierten Zählschleife.

Der Startwert für i ist in jedem Durchgang des Blocks c1c1 der aktuelle Wert von delta 6, und läuft jeweils bis n1n - 1.

In einem kompletten Durchlauf der Schleife entspricht die Anzahl der Aufrufe von c2c2 also

(n1)delta+1=ndelta(n - 1) - delta + 1 = n - delta

info

Hinweis: Für das Beispiel betrachten wir der Einfachheit halber Feldlängen der Form 2p2^p. Für den allgemeinen Fall gilt für die Anzahl der Aufrufe von c2c2:

i=1lg(n)nn2i=nlg(n)i=1lg(n)n2i\sum_{i=1}^{\lfloor lg(n) \rfloor} n - \lfloor \frac{n}{2^i} \rfloor = n * lg(n) - \sum_{i=1}^{\lfloor lg(n) \rfloor} \lfloor \frac{n}{2^i} \rfloor

Für die Gesamtzahl der Aufrufe von c2c2 ergibt sich somit unter Berücksichtigung von c1c1

i=1lg(n)nn2i1\sum_{i=1}^{lg(n)} n - \frac{n}{2^{i-1}}

was nach Auflösen

nlg(n)n+1n * lg(n) - n + 1

entspricht, und für unser Beispiel

16lg(16)16+1=4916 * lg(16) - 16 + 1 = 49

ist.

info

Die Aufrufzahlen für c2c2 für verschiedene nn. Schlüsselvergleiche finden erst später statt. Mit n>2156n > 2156 wächst O(n43)O(n^\frac{4}{3}) schneller als c2c2 und mit n>=982n >= 982 schneller als O(n log n)O(n\ log\ n).

nc2O(n1.1)O(n^{1.1})O(n1.3)O(n^{1.3})O(n log n)O(n\ log\ n)O(n2)O(n^2)
8179142464
1649213664256
3212945901601024
64321972223844096
12876920754889616.384
25617934451351204865.536
1024921720488192102401.048.576
215621.5654.645,2921.564,6923.875,844.648.336
215721.5764.647,6621.577,7023.888,364.652.649
215821.5864.650,0321.590,7023.900,884.656.964
..................
10.000120.00525.118158.489132.8771.0E8
100.0001.500.006316.2273.162.2771.660.9641.0E10
200.0003.200.006677.8497.786.4403.521.9284.0E10
500.0008.500.0071.857.2352.56..E79.465.7842.5E11
1.000.00018.000.0073.981.0716.30..E71.99..E71.0E12

In der while-Schleife in Zeile 17 findet die eigentliche Arbeit des Algorithmus statt: Es wird überprüft, ob deltadelta-entfernte Elemente in aufsteigender Reihenfolge sortiert angeordnet sind.

Ist das nicht der Fall, werden die Elemente an den Stellen jj und jdeltaj - delta ausgetauscht, bis die hh-Folge sortiert ist.
Für den ersten Durchgang des Algorithmus an dieser Stelle mit h4=8h_4 = 8 ergibt sich somit die in Abbildung 3 dargestellte Reihenfolge der Schlüssel:

Figure 3 Nach dem ersten Durchgang sind die Schlüssel in den Abständen h4 = 8 sortiert, es ergeben sich zwei sortierte Teilfolgen der Länge 8.

Die weiteren Durchgänge des Algorithmus sortieren das Feld entsprechend der Größe hh: Es sind danach jeweils Schlüssel mit den Abständen 44 (Abbildung 4 und 22 (Abbildung 5) sortiert; im letzten Schritt dann vollständig (Abbildung 6):

Figure 4 Die Sortierung für h3 = 4, es sind 4 Folgen deren Schlüssel jeweils den Abstand 4 zueinander haben.
Figure 5 Im vorletzten Sortierschritt sind 8 Folgen der Länge 2 sortiert.
Figure 6 Der letzte Durchgang des Algorithmus vergleicht Schlüssel mit Distanzfolgen der Länge 1, also direkt benachbarte Schlüssel.

Für die Berechnung der Anzahl der Aufrufe von c3c3 stellt man fest, das in diesem Fall in jedem Schritt immer 2 Elemente, die eine Distanz von hsh_s aufweisen, falsch sortiert sind.

Der Algorithmus tauscht daraufhin in jedem Durchgang alle Schlüssel untereinander aus, die er über min < arr[j-delta] miteinander vergleicht, was folglich die maximale Anzahl von Schlüsselvertauschungen in dieser vergleichsbasierten Implementierung für ein Feld der Größe nn ergibt, nämlich n2\frac{n}{2}. Insgesamt finden dadurch für c3c3

lg(n)n2lg(n) * \frac{n}{2}

Aufrufe statt.

Mit der Anzahl der berechneten Aufrufe c1,c2,c3c1, c2, c3 ergibt sich somit für die Laufzeit T(n)T(n) für diesen Fall

lg(n)+nlg(n)n+1+lg(n)n2lg(n) + n * lg(n) - n + 1 + lg(n) * \frac{n}{2}

und zusammengefasst

f(n)=32nlg(n)+lg(n)n+1f(n) = \frac{3}{2} * n * lg(n) + lg(n) - n + 1

was nach Einsetzen zu

lg(16)+16lg(16)16+1+lg(16)162=85lg(16) + 16 * lg(16) - 16 + 1 + lg(16) * \frac{16}{2} = 85

Aufrufen für unser Beispiel führt.

Nachweis der Komplexitätsklasse

Um OO zu ermitteln, werden nun alle Konstanten der Funktion

f(n)=32nlg(n)+lg(n)n+1f(n) = \frac{3}{2} * n * lg(n) + lg(n) - n + 1

eliminiert, und der "dominante" Summand in Abhängigkeit von nn betrachtet, der in diesem Fall lg(n)nlg(n) * n ist.

Wir vermuten ein NlogNN-log-N-Wachstum7 (vgl. [📖OW17a, p. 5]), und wollen nun zeigen, dass T(n)T(n) in O(n log n)O(n\ log\ n) liegt.
Hierfür müssen wir ein geeignetes cc und ein n0n_0 finden, so dass gilt:

fO(n log n):n0N,cR,c>0:nn0:f(n)cnlg(n)f \in O(n\ log\ n): \leftrightarrow \exists n_0 \in \mathbb{N}, c \in \mathbb{R}, c > 0: \forall n \geq n_0: f(n) \leq c * n*lg(n)

(vgl. [📖GD18a, p. 11]).

Zu zeigen ist

32nlg(n)+lg(n)n+1cnlg(n)\frac{3}{2} * n * lg(n) + lg(n) - n + 1 \leq c * n * lg(n)

Wir wählen für n0=1n_0 = 1 und c=32c = \frac{3}{2}, denn es gilt sicher

nn0:32nlg(n)32nlg(n)\forall n \geq n_0: \frac{3}{2} * n * lg(n) \leq \frac{3}{2} * n * lg(n).

Ausserdem gilt stets nN:lg(n)<n\forall n \in \mathbb{N}: lg(n) < n, woraus lg(n)n<0lg(n) - n < 0 folgt, und damit auch lg(n)n+10lg(n) - n + 1 \leq 0.

Insgesamt gilt also

n0=1,c=32:nn0:32nlg(n)+lg(n)n+1cnlg(n)n_0 = 1, c = \frac{3}{2}: \forall n \geq n_0: \frac{3}{2} * n * lg(n) + lg(n) - n + 1 \leq c * n * lg(n)

womit f=O(nlog(n))f = O(n * log(n)) gezeigt ist. ◻

Worst-Case-Analyse

Unter der Annahme, dass ein in umgekehrter Reihenfolge sortiertes Feld zu einer Laufzeit von O(n2)O(n^2) bei dem Shellsort-Algorithmus führt, konnten wir mit dem in dem vorherigen Abschnitt gewählten Parametern nur eine Laufzeit von O(n log n)O(n\ log\ n) nachweisen.
Tatsächlich stellt der Anwendungsfall nicht den worst-case für den Algorithmus dar, da ja gerade diese Form von Sortierreihenfolge dem Algorithmus die Vorsortierung der hh-Folgen ermöglicht:

The idea underlying Shellsort is that moving elements of A long distances at each swap in the early stages, then shorter distances later, may reduce this O(n2)O(n^2) bound. [📖Pra72, p. 3]

Es gilt also, die Vorsortierung auszuhebeln.
Für Insertion-Sort ist die Laufzeit im worst-case O(n2)O(n^2) (vgl. [📖OW17b, p. 87]). Da Shellsort mindestens im letzten Schritt diese Sortiermethode auf Distanzfolgen der Länge 11 anwendet, muss der Algorithmus eine Folge als Eingabe erhalten, die durch die ersten lg(n)1lg(n) - 1-Durchgänge (mit hs=2s1,1s<lg(n)h_s = 2^{s - 1}, 1 \leq s < lg(n)) keine Änderungen erfährt, um dann im allerletzten Schritt auf einen Schlag sortiert wird, was maximal n2\frac{n}{2} Inversionen8 bedeutet, und damit ebenso viele Vertauschungen (zuzüglich der benötigten Verschiebe-Operationen).
Hierzu kann wie im vorherigen Beispiel für n=16n=16 ein Feld mit folgender Schlüsselanordnung verwendet werden: Felder mit geradem Index enthalten kleinere Schlüssel als Felder mit ungeradem Index. Hier gilt für alle Elemente aus dem Feld AA:

i,jN[0,n1],2i,2j:A[i]<A[j]A[i]<A[i+1]A[j]<A[j+1]\forall i, j \in \mathbb{N}_{[0, n - 1]}, 2 \mid i, 2 \nmid j: A[i] < A[j] \land A[i] < A[i + 1] \land A[j] < A[j +1]

Abbildung 7 veranschaulicht die Anordnung.

Figure 7 Eine worst-case Schlüsselfolge für Shellsort. Felder mit geradem Index enthalten kleinere Schlüssel als Felder mit ungeradem Index.

Markiert sind die direkt benachbarten Felder, die eine Inversion aufweisen, die im letzten Schritt des Algorithmus eine bzw. mehrere Verschiebungen bedingen.
In den vorherigen Schritten - also bei den Durchgängen mit Distanzfolgen hs>1h_s > 1 - findet der Algorithmus jeweils Schlüssel in korrekter Sortierreihenfolge vor.

Mit h4=8h_4 = 8 werden die Felder A[0..7]A[0..7] mit den Feldern A[8..15]A[8..15] verglichen - hier gilt in jedem Fall, dass die Schlüssel A[i]<A[j](i<j,ji=8)A[i] < A[j] (\forall i < j, j - i = 8) sind.

Auch im darauffolgenden Durchgang (h3=4,ji=4h_3 = 4, j - i = 4) finden keine Verschiebungen statt, da keine Inversion gefunden wird. Erst im letzten Schritt, in dem direkt benachbarte Elemente miteinander verglichen werden, werden die Inversionen ermittelt und die Verschiebung der Elemente findet statt (s. Abbildung 8.

Figure 8 Für die worst-case Schlüsselfolge werden im letzten Schritt 7 Inversionen festgestellt. Jede dieser Fehlstellung bedingt eine Verschiebung um die angegebene Anzahl von Positionen.

In diesem Fall wird c3c3 insgesamt 3232 mal aufgerufen.

Da jeweils zwei Schlüssel bereits korrekt sortiert sind (A[0]A[0] und A[n1]A[n-1]) existieren noch n21\frac{n}{2} - 1 Inversionen. Jede Inversion erzwingt eine Verschiebung des größten Elements um i2\frac{i}{2} Positionen nach links.

Für die Berechnung der Laufzeitkomplexität ergibt sich somit der Term

i=1n21i=n2(n21)2=n22n8\sum_{i=1}^{\frac{n}{2} - 1} i = \frac{\frac{n}{2}(\frac{n}{2} - 1)}{2} = \frac{n^2 - 2n}{8}

und unter Berücksichtigung der Terme für c1c1, c2c2, c3c3 die Funktion

f(n)=lg(n)+nlg(n)n+1+n22n8f(n) = lg(n) + n * lg(n) - n + 1 + \frac{n^2 - 2n}{8}

was zu einer Laufzeitabschätzung von O(n2)O(n^2) führt.


  1. mit n=n = Länge des zu sortierenden Feldes. Im folgenden lglg für log2log_2.
  2. vgl. [📖Knu97c, p. 84]
  3. Knuth bezieht sich hier auf die Arbeit von Papernov und Stasevich ([📖PS65]). Weitere Verweise auf Laufzeiten in Abhängigkeit von nn und hh fasst übersichtlich der Wikipedia-Artikel zusammen: https://en.wikipedia.org/wiki/Shellsort (abgerufen 23.01.2024).
  4. Shell führt in seinem Paper keinen Beweis auf. Er stützt seine Behauptung auf Messungen, die er selber in Tests durchgeführt hat: "[...] an analytical determination of the expected speed has eluded the writer. However, experimental use has established its speed characteristics." (ebenda)
  5. hier wie im folgenden ohne Betrachtung der Schleifenbedingung, die an dieser Stelle insgesamt lg(n)+1lg(n) + 1-mal aufgerufen wird
  6. 8,4,2,1{8, 4, 2, 1} für das gegebene Beispiel
  7. mit O(log n)O(log\ n) bzw O(n log n)O(n\ log\ n) nehmen wir für die OO-Notation wieder die in der Fachliteratur gebräuchlichere Schreibweise auf. Sowohl Güting und Dieker als auch Ottmann und Widmayer weisen in [📖GD18a, p. 15] bzw. [📖OW17a, p. 5] darauf hin, dass die Angabe der Basis keine Rolle spielt, da sich Logarithmen mit verschiedenen Basen ohnehin nur durch einen konstanten Faktor unterscheiden (es gilt loga(x)=logb(x)logb(a)log_a(x) = \frac{log_b(x)}{log_b(a)}).
  8. in diesem Zusammenhang bedeutet Inversion: Fehlstellung (vgl. [📖OW17b, p. 87])