Skip to main content

One post tagged with "datastructures"

View All Tags

[DE] Shellsort Laufzeitanalyse

· 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) Inkremente[^1] hth_t[^2] 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.