Laufzeitkomplexität

Die Laufzeitkomplexität des Algorithmus hängt stark von der verwendeten Berechnungsweise des Wertes für h.

Mit einer Berechnung $h~=~\frac{h}{3}$ ergeben sich folgende Werte für die Anzahl der Tausch- und Vergleichsoperationen. (Diese Werte wurden mit der hier gezeigten Implementierung gewonnen.) Auch diesmal wurden die Tests auf der gleichen Datenmenge ausgeführt. Um das Verhalten des ShellSorts zum InsertionSort gegenüber zu stellen, seien in der folgenden Tabelle auch die Werte für diesen aufgelistet. Der Unterschied zwischen den Test ergibt sich aus der Vorsortierung der Datanmenge.

Elemente Vergleiche Tauschoperationen
  Insertion Shell Insertion Shell
 
aufsteigend vorsortiert
5 4 6 0 8
10 9 16 0 18
100 99 379 0 384
1000 999 5907 0 5914
10000 9999 80159 0 80168
 
absteigend vorsortiert
5 10 7 10 12
10 45 24 45 33
100 4950 546 4950 600
1000 499500 9131 499500 9565
10000 49995000 114018 49995000 119624
 
nicht vorsortiert
5 9 8 7 11
10 26 22 19 26
100 2632 1036 2538 1079
1000 254549 22507 253556 22872
10000 24536947 489860 24526954 493667


Unschwer zu erkennen ist, daß der ShellSort auf größeren Datenmenge wesentlich niedrigere Arbeitsschritte durchführt, wenn die zu sortierende Menge nicht in der Sortiertrichtung schon geornet ist. Es erweist sich ein unakzeptables Laufzeitverhalten des ShellSorts sofern er auf bereits sortierten Mengen operiert, wie in der ersten Tabelle ersichtlich wird.

Eine bessere Folge von h wäre eine bestehend aus Primzahlen. Der Hibbard's Increment mit einer Berechnung der Folge mit $2^k~-~1$ schafft eine Laufzeit von $O(n^{\frac{3}{2}})$, wobei nicht alle durch diese Formel generierten Zahlen Primzahlen sind.

Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: Implementierung Aufwärts: ShellSort Vorherige Seite: Beispiel   Inhalt

2002-05-09